Bug in PriorityQueue::remove() about priority-queue HOT 3 CLOSED

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)

from priority-queue.

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?

from priority-queue.

You are right

from priority-queue.