garro95/priority-queue

Bug in PriorityQueue::remove()

michalsrb opened this issue · 3 comments

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.

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)

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?

You are right