Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Bug in PriorityQueue::remove() #28

Closed
michalsrb opened this issue Dec 15, 2020 · 3 comments
Closed

Bug in PriorityQueue::remove() #28

michalsrb opened this issue Dec 15, 2020 · 3 comments
Labels

Comments

@michalsrb
Copy link

The PriorityQueue::remove() does not work correctly in some cases.

Here is minimal reproducer:

use std::collections::hash_map::RandomState;

use priority_queue::PriorityQueue;

fn main() {
    let mut queue = PriorityQueue::<i32, i32, RandomState>::default();

    for i in 0..7 {
        queue.push(i, i);
    }

    queue.remove(&0);

    let mut last_priority = *queue.peek().unwrap().1;
    while let Some((i, priority)) = queue.pop() {
        dbg!(priority);
        assert!(last_priority >= priority);
        last_priority = priority;
    }
}

This will pop elements in order 6, 5, 3, 4, which is clearly not correct.

I have partially debugged it and I think the map, heap and qp are updated correctly and remain consistent, but the actual algorithm for removing element from heap is not correct. It seems that the remove() function assumes that heapify() will perform up-heapify or down-heapify as needed, but it in fact only performs down-heapify. So in the case when up-heapify should have happened, the "heap" vector is no longer an actual heap.

garro95 pushed a commit that referenced this issue Dec 16, 2020
@garro95
Copy link
Owner

garro95 commented Dec 16, 2020

Thank you for your bug report. The problem was in fact that the heapify operation should be only a down-heapify, but starting at the parent of the removed element.

Can I use your minimal reproducer as a test case? (It will be distributed as the library under both the LGPLv3 or later and MPLv2)

garro95 pushed a commit that referenced this issue Dec 16, 2020
Add actual fix of #28
@michalsrb
Copy link
Author

Of course, you can use it as a test case.

Are you sure that the down-heapify from the parent is enough? Consider heap like this:

           20
      7            19
    5   6      15     18
   1 2 3 4   13  14  16  17

As array: 20 7 19 5 6 15 18 1 2 3 4 13 14 16 17

If you remove the number 1, it gets replaced with 17 and that should filter up two levels. Filtering down from the parent won't do it. Unless there is something I am missing that prevents a heap like this in the first place?

@garro95
Copy link
Owner

garro95 commented Dec 16, 2020

You are right

@garro95 garro95 reopened this Dec 16, 2020
@garro95 garro95 added the bug label Mar 19, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants