Stop 20 · Data Structures & AlgorithmsTopics · 8/8

Heaps

In short

Top 10 search results, the next job in a queue, the k closest points to a query: whenever you keep asking "what's the smallest or biggest right now?", a heap answers in a blink.

A tree-based structure that efficiently tracks the min/max element — used for problems involving top-K elements, scheduling, or streaming statistics.

The purple blob at an emergency desk waves a patient on a stretcher ahead of patients with small bandages.

Think of it like this

The hospital emergency desk

In an emergency ward, patients aren't seen in arrival order. The nurse always calls the most serious case next. A new patient with chest pain jumps ahead of someone with a sprained wrist. A heap works the same way: it always hands you the most urgent item first.

Watch it happen

Pushing 1 into a min-heap

1/5A min-heap stored as an array. The smallest value, 2, sits at index 0. Each parent is smaller than its children.

The big ideas

What you need to know

A tree hiding in an array

Children of index i are at 2i + 1 and 2i + 2. No pointers needed, just arithmetic.

Fast where it counts

Peek at the top in O(1). Push and pop in O(log n). Searching for a random value is still slow.

Python's heapq is a min-heap

For a max-heap, push negative values, or tuples like (-priority, item).

Top-k in O(n log k)

Keep a min-heap of size k. If it grows past k, drop the smallest. What's left are the k biggest.

See it in code

Walk through the code

python

1import heapq2 3def top_k(scores, k):4    heap = []                      # min-heap of the k best so far5    for s in scores:6        heapq.heappush(heap, s)7        if len(heap) > k:8            heapq.heappop(heap)    # drop the smallest9    return sorted(heap, reverse=True)10 11print(top_k([0.91, 0.42, 0.77, 0.98, 0.65], 3))  # [0.98, 0.91, 0.77]12 13# Max-heap trick: push negatives14urgent = []15heapq.heappush(urgent, (-9, "chest pain"))16print(heapq.heappop(urgent))  # (-9, 'chest pain')

1/3The heap never holds more than k items, so memory stays tiny.

Top-k with a small heap is how you keep the best few similarity scores without sorting millions of them. heapq.nlargest does the same in one call.

Save yourself the pain

Common mistakes

Oops

Sorting the whole list every time a new item arrives.

Do this instead

That's O(n log n) per insert. A heap gives you push and pop in O(log n) while keeping the top ready.

Oops

Thinking heap[1] is the second smallest item.

Do this instead

Only heap[0] is guaranteed. The rest is just partly ordered. Pop twice to get the second smallest.

Your mission

Three heap classics

~40 min

Quick check

You want the 10 highest scores from a stream of 10 million. What's the smartest approach?

Go deeper

1Practice using a heap for top-K and 'k closest' style problems.
2Learn Python's `heapq` module (or equivalent) fluently.
3Understand when a heap beats sorting the whole array (streaming or partial-order needs).