Priority Queue With a Heap

As you probably noticed, the API of our new MinHeap class is very similar to the API of our PriorityQueue class. In fact, a heap is an ideal structure for a priority queue.

Remember that our original naïve implementation of a priority queue was just a list. It had the following Big O complexities:

• push: O(1)
• peek: O(n)
• pop: O(n)

Once we upgraded to a min heap, we got the following time complexities:

• push: O(log(n))
• peek: O(1)
• pop: O(log(n))

The difference between O(log(n)) and O(n) is huge!

Imagine we need to pop a value from a priority queue with 1 million elements:

• With the O(n) implementation, we need to look at all 1 million elements to find the one with the lowest priority.
• With the O(log(n)) implementation, we access the lowest-priority element immediately at the root, then we only need ~20 operations to maintain the heap structure. That's about 50,000x faster!

It may look like we're sacrificing time complexity on push, but at scale, the difference between O(1) and O(log(n)) is much smaller than the difference between O(log(n)) and O(n). This is important to keep in mind when choosing data structures and algorithms.