Always knowing the smallest
A hospital waiting room does not call patients in the order they arrived. It calls the most urgent. New patients keep arriving, and each time the question is the same: who is most urgent right now?
Keeping everyone fully sorted would answer it, but sorting is more work than needed. You never ask who is 7th. You only ever ask for the top one.
A heap is built for exactly that. It supports two operations, both fast:
- insert a new item, and
- remove the smallest item.
This page uses a min-heap, where the smallest is on top. A max-heap is the same idea turned upside down.
The one rule
A heap is a tree where every parent is smaller than its children. That is the only rule. Brothers and sisters can be in any order.
Follow the rule up the tree and one thing is guaranteed: the smallest value of all sits at the top.
The tree is also kept complete: every level is full except possibly the last, which fills from the left. That shape matters for the next two operations.
The same heap as it is really stored: one array
Start. A min-heap. The rule: every parent is smaller than its children. So the smallest value is always at the top.
Insert: add at the bottom, swap upwards
Put the new value in the first free spot
The bottom of the tree, as far left as possible. The shape stays complete.
Compare it with its parent
If it is smaller, the rule is broken. Swap them.
Repeat from its new position
Stop when the parent is smaller, or when it reaches the top.
Remove the smallest: move the last to the top, swap downwards
Take the top value. That is the answer
It leaves a hole at the root.
Move the last value into the hole
The shape is complete again, but the rule is probably broken at the top.
Compare it with its children and swap with the smaller one
The smaller child must go up, or it would end up above its own brother.
Repeat until it is smaller than its children
Or until it has no children.
Both operations follow one path between the top and the bottom. A complete tree with a million items is only 20 levels deep, so each takes at most about 20 swaps.
It is secretly an array
A complete tree has no gaps, so it can be stored level by level in a plain array with no pointers at all. For the item at position i:
| Relation | Position |
|---|---|
| Its left child | 2 * i + 1 |
| Its right child | 2 * i + 2 |
| Its parent | (i - 1) // 2 |
import heapq
waiting = []
heapq.heappush(waiting, (2, "sprained ankle")) # (priority, patient)
heapq.heappush(waiting, (1, "chest pain"))
heapq.heappush(waiting, (3, "paperwork"))
heapq.heappop(waiting) # (1, "chest pain")Good at
- Insert and remove-smallest both take a number of steps that grows very slowly with size
- Looking at the smallest (without removing it) is instant
- One compact array, no pointers
Where it bites
- Finding any other item means searching the whole thing
- It is not sorted: only the top is in a known place
Where you will meet it
- Priority queues: task schedulers, and timers that must fire in order.
- Shortest routes: Dijkstra's algorithm keeps the places still to visit in a heap, nearest first.
- Top 10 of a million: keep a heap of the 10 best seen so far and compare each new item only with the worst of those.
- Heapsort: put everything in a heap, then remove the smallest again and again.
Key takeaways
- A heap keeps the smallest item at the top without keeping everything sorted.
- The rule: every parent is smaller than its children.
- Insert adds at the bottom and swaps upwards. Remove takes the top, moves the last item there, and swaps downwards.
- Both follow one path through the tree, so they stay fast as the heap grows.
- The tree is stored as a flat array, with children at 2i + 1 and 2i + 2.