When should you use a heap?

Reach for a heap when a problem keeps asking for the smallest or largest of what's left — while values are still being added or removed. Sorting answers that question once. A heap answers it again and again, at O(log n) per change.

A table comparing three ways to keep values. A plain array finds the smallest in O(n), adds in O(1) and removes the smallest in O(n). A sorted array finds and removes the smallest in O(1) but adds in O(n), because values must shift. A heap finds the smallest in O(1) and adds or removes in O(log n). — A heap is never the fastest at any one thing, but it's never slow at any of them.

That last row is the whole reason heaps exist. When a problem mixes adding values with taking out the smallest (or largest), the other two choices each have one operation that costs O(n) — and a loop that does it n times costs O(n²).

The signals

“k largest”, “k smallest”, “top k”, “k closest”, “k most frequent” — keep a heap of size k.
“Repeatedly take the smallest (or largest)” — join the two shortest ropes, smash the two heaviest stones, run the most urgent task. A greedy choice made again and again.
“Merge k sorted …” — a heap holds the front of each list and always hands you the smallest of them.
A stream with a running answer — the kth largest so far, the median so far. Each new value costs O(log n).
Scheduling and shortest paths — events ordered by time, tasks by priority, Dijkstra's next-closest node.

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 6 more sections, 4 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

Pattern 1: top k with a heap of size k
Pattern 2: always take the smallest (or largest)
Pattern 3: merge k sorted sources
Pattern 4: two heaps for a running middle
When a heap is the wrong tool
Key takeaways

Prev Next

Mark completed

Was this helpful?

When should you use a heap?

The signals

Keep reading. It's free.

Keep exploring