How to preserve the order of elements of the same priority in a priority queue implemented as binary heap?

17
votes

I have created a binary heap, which represents a priority queue. It's just classical well known algorithm. This heap schedules a chronological sequence of different events ( the sort key is time ).

It supports 2 operation: Insert and Remove. Each node's key of the heap is greater than or equal to each of its children. However, adding events with the same key doesn't preserve the order they were added, because each time after Remove or Insert were called, the heap-up and the heap-down procedures break the order.

My question is: what should be changed in a classical algorithm to preserve the order of the nodes with the same priority?

3
calgorithmpriority-queuebinary-heap
suppose you add a new element with a priority which already exists.. what's going to be the order? – Karoly Horvath
add another field called insert order (long long) and it's always incremented when you Insert. so you end up w/ pair for final key: priority+insert order – bestsss

3 Answers

17
votes

One solution is to add time of insertion attribute to the inserted element. That may be just a simple counter incremented each time a new element is inserted into the heap. Then when two elements are equal by priority, compare the time of insertion.

2
votes

As far as I know, heaps are never built to preserve order (which is why "heap sort" is notable for not being a stable sort).

I understand that what you are asking is whether a small algorithmic trick might be able to change this (that is not the good old reliable "timestamp" solution). I don't think it's possible.

What I would have suggested is some version of this:

  • keep the same "insert";

  • modify "remove" so that it ensures a certain order on elements of a given priority.

To do this, in heap-down, instead of swapping elements down until the order is preserved: swap an element down until it as the end of an arborescence of elements of the same value, always choosing to go to the right when you can.

Unfortunately the problem with this is that you don't know where insert will add an element of a given priority: it could end up anywhere in the tree. Changing this would be, I believe, more than just a tweak to the structure.

0
votes

If the elements are inserted in chronological order and this order is maintained (for example by having "append" rather than "insert" and "remove_and_pack" rather than just "remove") you could use the memory address (cast to an unsigned 32- or 64-bit integer depending on environment) of the element as the final comparison step. Early elements will have numerically lower addresses than later ones.