Despite the fact that I've got a BS in Computer Science (and this was covered in the university), I've never been able to understand the relationship between binary heaps and priority queues. It just... doesn't click. I completely understand what a binary heap is and I know how to implement one in an array. I also know what a priority queue is. But how do the two of them fit together?
A quick google query shows a lot of articles like this one. Which kind of explains it, yet I'm left more questions:
What am I missing here?
A priority queue is an abstract data type like "stack" or "associative array." There can are many different ways to implement a priority queue - you can use binary heaps, binomial heaps, Fibonacci heaps, pairing heaps, etc.
I don't believe that there is any intrinsic requirement that a priority queue be "stable" and require that elements with equal priorities be dequeued in the same relative order in which they were added, much in the same way that there's no instrinsic requirement that a sorting algorithm be stable (though many are). It's a nice property to have, but usually it's not guaranteed. This is why, for example, a standard heapsort isn't a stable sort.
Fortunately, it's not too hard to adjust binary heaps to be stable. Keep a counter associated with the binary heap. Whenever you add an element to the heap, tag it with the current value of the counter and increment the counter. When doing heap operations, use the counter as a tiebreaker to determine which value is smaller if two values compare equal. Essentially, this changes the comparison to a lexicographical comparison first on the real value and then on the insertion order.
Hope this helps!
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments