computer-science/heaps-how-a-computer-always-knows-the-most-urgent-item-without-sorting.md
Heaps: how a computer always knows the most urgent item without sorting everything
A hospital waiting room, a game's task list and a map app all need the same thing: the most urgent item, right now, while new items keep arriving. Scanning everything each time is slow, and keeping a full sorted list is costly to maintain.
A *heap* keeps just enough order to hand you the smallest item instantly. Add numbers to a live heap, watch each one float up or sink down one swap at a time, and see why a million items need only about 20 steps. Includes real Python `heapq` code with its output.

Who goes next?
Picture a hospital waiting room. People arrive all day, and each one gets a priority number: 1 is the most urgent, 9 can wait. Whenever a doctor becomes free, the staff must call the most urgent person who is still waiting. New people keep arriving in between.
Programs have this problem everywhere: an operating system choosing which task to run next, a game choosing which enemy to update first, a map app choosing which road to explore next. The structure that solves it is called a priority queue (a waiting line where the most urgent item leaves first, not the oldest). The most common way to build one is a heap. Here is how it works, and why it is fast.
Two obvious ways, and where they hurt
Keep the waiting people in a plain list. To find the most urgent one, look at every item: with 1,000,000 people that is 1,000,000 looks, every single time a doctor is free. Or keep the list sorted, so the winner is always at the front. Finding it is instant, but now every new arrival must be slotted into the right place, and that can mean shifting a huge number of items along.
A heap sits in the middle. It does not keep everything sorted. It keeps only as much order as it needs to hand you the smallest item immediately, and it repairs that order cheaply after each change.
The one rule
A min-heap is a tree where every item is smaller than or equal to the items below it (its children). The item above it is its parent. That is the whole rule. It guarantees that the smallest item of all sits at the very top, because nothing can be smaller than the top without breaking the rule.
Notice what the rule does not say: two items on different branches can be in any order. A heap is not a sorted list, and that looseness is exactly what makes it cheap to maintain.
The tree is also kept tidy: it fills row by row from left to right, with no gaps. That lets us store it in an ordinary list with no pointers at all. Item number i (counting from 0) has its parent at (i - 1) // 2 and its children at 2*i + 1 and 2*i + 2.
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 1 | 3 | 9 | 7 | 5 |
| children | 1, 2 | 3, 4 | none | none | none |
Index 0 (value 1) has children at indexes 1 and 2 (values 3 and 9). Index 1 (value 3) has children at indexes 3 and 4 (values 7 and 5). Every parent is smaller than its children, so the rule holds.
Try it: add and take
Below is a live heap. Add a number and press Next step to watch it repair the order one comparison at a time, or press Take smallest to remove the top item. The tree and the list underneath are the same data drawn two ways.
What just happened
Adding puts the new item in the next open spot at the bottom, which keeps the tree tidy. Then it sifts up: while the item is smaller than its parent, swap them. It stops as soon as the parent is not bigger, which is often after zero or one swap.
Taking the smallest is always the top item, so there is nothing to search for. But removing it leaves a hole. The trick is to move the last item of the list into the hole, which keeps the tree tidy, and then sift down: while the item is bigger than a child, swap it with its smaller child. Swapping with the smaller child matters: it is the only choice that leaves the other child still larger than its new parent.
Keep pressing Take smallest and read the "Taken out" line. The numbers come out in order, smallest first, even though the list was never sorted.
Why it is fast
Each swap moves an item exactly one row, and the tree is packed, so it has very few rows. Every row holds twice as many items as the one above it. The row count is the number of times you can keep doubling before you pass the number of items:
| items | rows in the tree | most swaps for one add or take |
|---|---|---|
| 1,000 | 10 | 9 |
| 1,000,000 | 20 | 19 |
| 1,000,000,000 | 30 | 29 |
So a million waiting items cost about 20 steps to repair, compared with a million looks for the plain list. Computer scientists write this growth as O(log n), which means "the work grows by a tiny step each time the data doubles".
The same thing in Python
Python's standard library has this built in, in the heapq module. It stores the heap in an ordinary list, exactly like the table above:
import heapq
tasks = [7, 3, 9, 1, 5]
heap = []
for t in tasks:
heapq.heappush(heap, t)
print(heap)
print(heapq.heappop(heap))
print(heapq.heappop(heap))
print(heap)
Output when we ran it:
[1, 3, 9, 7, 5]
1
3
[5, 7, 9]
That first line is the same list you started with in the figure. Here is the idea written out by hand, so you can see that sifting is only a few lines:
def push(heap, value):
heap.append(value)
i = len(heap) - 1
while i > 0:
parent = (i - 1) // 2
if heap[parent] <= heap[i]:
break
heap[parent], heap[i] = heap[i], heap[parent]
i = parent
def pop_min(heap):
smallest = heap[0]
last = heap.pop()
if heap:
heap[0] = last
i = 0
while True:
left, right = 2 * i + 1, 2 * i + 2
small = i
if left < len(heap) and heap[left] < heap[small]:
small = left
if right < len(heap) and heap[right] < heap[small]:
small = right
if small == i:
break
heap[i], heap[small] = heap[small], heap[i]
i = small
return smallest
h = []
for n in [7, 3, 9, 1, 5]:
push(h, n)
print(h)
print(pop_min(h), pop_min(h))
print(h)
Output when we ran it:
[1, 3, 9, 7, 5]
1 3
[5, 7, 9]
It matches heapq exactly. One detail worth knowing: heapq is always a min-heap. To get the biggest item first, store each number with its sign flipped (push -7 instead of 7) and flip it back when you take it out.
When to reach for a heap
Use one when you repeatedly need "the smallest (or most urgent) thing right now" while new things keep arriving: task schedulers, event timers, and path-finding algorithms such as Dijkstra's all work this way. Python's heapq.nsmallest(10, data) uses the same idea to pick the 10 smallest of a huge list without sorting all of it.
Know the limits too. A heap only knows its top. Asking "is the number 42 in here?" means scanning the whole list, so a heap is the wrong tool for lookups. And if you need every item in sorted order once, a plain sorted() call is simpler and does the job.