Heaps and priority queues

Topics in this section
2 cards

Heaps: the smallest is always on top

A heap is a binary tree with one rule: every parent is smaller than or equal to its children (a min-heap; a max-heap flips it). Unlike a BST, there's no order between siblings, so you can't search a heap for an arbitrary key. What you get instead is instant access to the minimum: it's always the root.

Adding an item and removing the minimum are both O(log n): the new item bubbles up, or the item moved into the root sinks down, along one path. And a heap is stored as a plain array, no pointers: the children of position i are at 2i+1 and 2i+2.

A min-heap of seven numbers drawn as a tree and stored as an array
In real life

A hospital emergency room: the next patient isn't whoever came first but whoever is most urgent. New patients arrive constantly, and the most urgent one must be found instantly.

In code: Python · Rust
import heapq
er = []
heapq.heappush(er, (2, "broken arm"))   # (priority, item)
heapq.heappush(er, (1, "chest pain"))
heapq.heappush(er, (3, "cough"))
heapq.heappop(er)    # (1, 'chest pain'): smallest first

heapq.nsmallest(2, [5, 1, 4, 2])   # [1, 2]
  • Python's heapq is a min-heap over a plain list; Rust's BinaryHeap is a max-heap. A common source of bugs when switching languages.
  • Tuples compare element by element, which is why (priority, item) works as a heap entry.
Check yourself

What can a min-heap do quickly that a hash map cannot?

Priority queues in real systems

A priority queue is the abstract idea, 'always take the most important item next', and a heap is how it's almost always implemented. Wherever work arrives in any order but must be handled by urgency, deadline or cost, a priority queue is underneath.

A classic interview pattern is top-K: keep the K largest items from a huge stream by holding a min-heap of size K. Each new item is compared with the heap's minimum; if it's larger, it replaces it. Memory stays at K, and each item costs O(log K), instead of sorting everything.

In real life

Job schedulers running the task with the earliest deadline; timers in a web server (which timeout fires next?); 'top 10 products by sales today' over millions of orders; route planners exploring the cheapest path first.

In code: Python · Rust
import heapq
def top_k(stream, k):
    h = []
    for x in stream:
        if len(h) < k:
            heapq.heappush(h, x)
        elif x > h[0]:
            heapq.heapreplace(h, x)   # pop the min, push x
    return sorted(h, reverse=True)

top_k([5, 1, 9, 3, 7, 8], 3)   # [9, 8, 7]
  • For a one-off answer in Python, heapq.nlargest(k, data) does the same thing.
  • Top-K with a heap of size K uses O(K) memory, which is what makes it work on streams too big to sort.
Check yourself

You need the 10 most expensive orders out of 50 million, reading them as a stream. What is the efficient approach?