Start here: the problem it solves#
TL;DRthe 30-second version
- You repeatedly need the smallest item from a bag that keeps changing. A sorted array is slow to insert into. An unsorted array is slow to find the minimum in.
- A binary heap only enforces that every parent is smaller than its children. So the smallest item is always the root.
- The tree is complete, so it lives in a plain array. Node i has children at 2i+1 and 2i+2 and a parent at (i−1)/2.
- Push appends and sifts up. Pop removes the root, moves the last leaf to the top, and sifts down. Each walks one root-to-leaf path, so both are O(log n).
You're writing a scheduler. Thousands of tasks are waiting, each with a time it should run. Every moment you ask the same question: which task is due soonest? Meanwhile new tasks keep arriving.
The obvious idea is a sorted array. The soonest task is the first element, which is instant. But inserting a new task means shifting everything after it down a slot. With 10,000 tasks that's up to 10,000 moves per insert.
So you try an unsorted array. Adding is cheap, you just append. But now finding the soonest task means scanning all 10,000 every time. You've moved the O(n) cost from insert to find-min, and find-min is the thing you do most.
Here's the way out. You never need the tasks fully sorted. You only ever look at the smallest. So keep them just ordered enough that the smallest is always easy to find.
The mechanism: a tree with one weak rule#
Arrange the items as a binary tree and enforce a single rule: every parent is smaller than both of its children. This is the heap property, and a tree that obeys it is a min-heap. (Flip the comparison and you get a max-heap.)
The rule does not sort the tree. Two siblings can be in any order. But it forces the single smallest item to sit at the root, because the root beats its children, which beat theirs, all the way down.
every parent is smaller than its children; the smallest key, 1, sits at the root
- 1i=0
- 3i=1
- 5i=3
- 9i=4
- 6i=2
- 8i=5
- 7i=6
- 3i=1
The second choice makes it cheap to store. Keep the tree complete, meaning every level is packed full except the bottom one, which fills from the left. A complete tree has no gaps, so it fits in a flat array in top-to-bottom, left-to-right order. No child or parent pointers are needed, just index arithmetic.
index: 0 1 2 3 4 5 6
value: 1 3 6 5 9 8 7
^root
children of index i: left = 2i+1, right = 2i+2
parent of index i: (i - 1) / 2
index 2 (value 6) -> children at 5 and 6 (values 8, 7)To push, put the new item in the next free array slot, the next leaf on the bottom row. It might be smaller than its parent. So sift it up: compare with the parent, swap if smaller, and repeat until the parent is smaller or you reach the root. Pushing 2 into the heap above lands it at index 7 under the 5, swaps past 5 and then 3, and stops below 1. Two swaps.
To pop, take the root, since that's the answer. Fill the hole by moving the last leaf up into the root and shrinking the array by one. That leaf is probably too big to be the root. So sift it down: compare with both children, swap with the smaller one if it's smaller than you, and repeat until both children are bigger or you hit a leaf. Popping from the heap above moves 7 to the root, then 7 sinks past 3 and past 5, and the heap is [3, 5, 6, 7, 9, 8].
PredictYou keep 10,000 pending timers in a min-heap keyed by fire-time. Roughly how many comparisons does one pop cost, and why isn't it close to 10,000?
Hint: How tall is a complete tree of 10,000 nodes?
About 25 to 30, not 10,000. A complete tree of 10,000 nodes is about log₂(10,000) ≈ 13 levels tall. Sift-down does roughly two comparisons per level (pick the smaller child, then compare it with the sinking value), so around 26. The heap only walks one root-to-leaf path. It never looks at the other timers.
If this comes up in an interview#
Is a heap the same as a sorted list?
No, and this is the most common mistake. Only the root is the extreme. The rest is not sorted, and reading the array left to right gives no useful order. The only way to get sorted output is to pop everything one at a time, which is exactly what heapsort does.
Can I find or update an arbitrary item quickly?
Not in a bare heap. The rule only relates parents to children, so a key could be anywhere. Search is O(n). The fix is an indexed heap: keep a map from item to its current array index, jump straight to it, and sift it up or down. That's what decrease-key in Dijkstra needs.
Why is build-heap O(n) and not O(n log n)?
Because you drop all n items in unordered and sift down from the last parent back to the root, instead of pushing n times. Most items sit near the leaves and barely move. Half do nothing, a quarter move one level, and the total sums to linear.
How do you find the k largest items in a huge stream?
Keep a size-k min-heap. For each new item, if it beats the root (the smallest of your current top-k), pop the root and push the newcomer. That's O(n log k) time and O(k) memory.
When to reach for one, and what it can't do
| Binary heap | Sorted array | Balanced tree / skip list | Hash table | |
|---|---|---|---|---|
| Get min/max | O(1) | O(1) | O(log n) | O(n) |
| Insert | O(log n) | O(n) | O(log n) | O(1) average |
| Remove min/max | O(log n) | O(n) | O(log n) | O(n) |
| Find arbitrary key | O(n) | O(log n) binary search | O(log n) | O(1) average |
| Sorted iteration / range | No (must drain) | Yes | Yes | No |
| Space overhead | None (array) | None (array) | Pointers per node | Load-factor slack |
| Best home | Priority queue / next-out | Static, read-mostly ordered | Ordered map with lookups | Unordered key lookup |
- Reach for a heap when the loop is 'repeatedly take the most extreme item while items keep arriving'. Python's heapq, Java's PriorityQueue, and C++'s std::priority_queue are all binary heaps.
- Timers are the classic case. The Go runtime keeps each processor's pending timers in a 4-ary min-heap keyed by fire-time, so 'which timer fires next' is the root. A larger branching factor makes the tree shorter and cache-friendlier.
- If you need sorted iteration or range queries, use a balanced tree or skip list. If you need lookup of arbitrary keys, use a hash table or pair the heap with one.
- If you only ever have a fixed small number of priorities, a bucket queue or timing wheel can be O(1) per operation.
References
- Wikipedia — Binary heap — the array layout, sift-up/sift-down, and the O(n) build-heap analysis
- Sedgewick & Wayne — Algorithms, 4th ed.: Priority Queues (Princeton) — heap-ordered arrays, swim/sink, and heapsort with worked code and proofs
- Python — heapq (heap queue) documentation — the standard-library binary min-heap over a list; nlargest/nsmallest and merge
- Go runtime — runtime/time.go (timer implementation) — per-processor 4-ary min-heap of timers; siftupTimer / siftdownTimer