How do you use a binary heap to implement a priority queue?

Question

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:

1. A priority queue needs to ensure that if two items with the same priority are added, then they will be removed in the same order that they were added. How does a binary heap ensure this? (In fact, if I'm not mistaken, then the border case where ALL the items have the same priority would produce a heap which would violate this rule).
2. What happens when you remove the root from the heap, then put in the last element in place of the root, and then need to swap it with one of the children - but both children have the same value. How do you pick which one to swap with? (Holding in mind the FIFO rule of same-priority items)

What am I missing here?

Answer 1

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!