Heaps as Priority Queues

Now that you understand how heaps work, we can circle back to our old friend, the priority queue.

Again, the primary function of a priority queue is to allow us immediate access to the highest-priority item in the queue. In our emergency room example, we want to first address the person with the most serious problem.

It’s for this reason that a heap is a natural fit for priority queue implementations. The heap gives us immediate access to the highest-priority item, which can always be found at the root node. Each time we take care of the highest-priority item (and then remove it from the heap), the next-highest item floats to the top of the heap and is on deck to be addressed next. And the heap accomplishes this while maintaining very fast insertions and deletions, both of which are O(log N).

Contrast this to the ordered array, which requires much slower insertions of O(N) to ensure that each new value is in its proper place.

It turns out that the heap’s weak ordering is its very advantage. The fact that it doesn’t have to be perfectly ordered allows us to insert new values in O(log N) time. At the same time, the heap is ordered just enough so that we can always access the one item we need at any given time, namely, the heap’s greatest value.