A priority queue is a data structure that holds a set of elements and can return quickly the smallest (or alternatively the largest) element. It is usually implemented using a binary heap.
So you “add” elements to the priority queue, and then you can “poll” them out.
Suppose however that you insert elements that are equal. What happens? Because binary heaps are not stable, your elements may not come out in insertion order.
For example, suppose you add the following tuples to a priority queue:
[{ name: 'player', energy: 10}, { name: 'monster1', energy: 10}, { name: 'monster2', energy: 10}, { name: 'monster3', energy: 10} ]
You could poll them back out based on their “energy” value in a different order… even though they all have the same “energy”…
[{ name: 'player', energy: 10}, { name: 'monster3', energy: 10}, { name: 'monster2', energy: 10}, { name: 'monster1', energy: 10} ]
That’s not very elegant.
Thankfully, there is an almost trivial approach to get a stable priority queue. Just add some kind of counter recording the insertion order, and when you insert elements in the binary heap, just use the insertion order as to differentiate elements. Thus, for a to be smaller than b, it is enough for the value of a to be smaller than the value b or that a be the same as b in value, but with a smaller insertion counter.
For example, we might store the following:
[{ value: { name: 'player', energy: 10 }, counter: 0 } { value: { name: 'monster1', energy: 10 }, counter: 1 } { value: { name: 'monster2', energy: 10 }, counter: 2 } { value: { name: 'monster3', energy: 10 }, counter: 3 }]
When comparing any two objects in this example, we not only compare them by their “energy” attribute, but also by their “counter” attribute.
So I implemented it in JavaScript as a package called StablePriorityQueue.js.
Easy!
I can’t promise that the performance will be as good as a speed-optimized priority queue, however.
This lead me to a follow-up question: what is the best (most efficient) way to implement a stable priority queue?
Since the standard binary heap does not support tracking the insertion order, we chose to append an insertion counter. That’s reasonable, but is it the most efficient approach?
And, concretely, what would be the best way to implement it in a given language? (Java, JavaScript…)
The ultimate goal would be to get a stable priority queue that has nearly the same speed as a regular priority. How close can we get to this goal?
Credit: Thanks to David Ang for inspiring this question.
There are some options discussed here: http://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap .
Thanks. I already link to this reference in my blog post. Do you think any of them is attractive as far as implementation goes?
Apologies for not noticing that — I made a mental bookmark to look through these later, but I haven’t looked in depth. So far Eppstein’s idea seems fairly costly, but the Fagerberg modification of Bentley-Saxe looks interesting.
Now that I’ve looked at Fagerburg, it doesn’t make sense — the binary representation of n does not match the bucket structure if one of the buckets has had all of its members deleted.
I haven’t looked at the links, so this might be redundant, but wouldn’t it work to have a priority queue of FIFO queues? All of the items in a particular FIFO queue would all have the same score. Of course there are lots of ways to implement a FIFO queue; pick your favorite.
Do you have an implementation (anything would do: Python, Perl, Ruby, JavaScript)?
Sorry, the idea I posted doesn’t work at all. When inserting a value that’s equal to a value already in the priority queue, there’s no guarantee that you’d stumble across the existing value.
One minor insight is that this looks a lot more like sorting than heapifying. For instance inserting the same value n times means that the entries either have to be sorted internally on insert (in some fully ordered structure like a BST), or they have to keep timestamp counters as you describe, so that they can be ordered on output.
A hybrid strategy is to sort them partially by timestamp on insert (into separate subqueues for each time range, say) and store the remaining lower-order time bits with each entry. The subqueues can then be managed in a queue-of-queues. There are some possible benefits in that only the newest subqueue accepts inserts, although I can see some costs too :(.