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

Computer science · 6 min read ·

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.

A min-heap drawn as a tree: the smallest number, 1, in green at the top with larger numbers below

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.

index01234
value13975
children1, 23, 4nonenonenone

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:

itemsrows in the treemost swaps for one add or take
1,000109
1,000,0002019
1,000,000,0003029

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.

$ ls computer-science/

see all →
computer-science/coin-change-why-grabbing-the-biggest-coin-first-can-fail-and-how-a-tab.md Coin change: why grabbing the biggest coin first can fail, and how a table fixes it A cashier owes 6 cents and has coins worth 1, 3 and 4. Grabbing the biggest coin first uses three coins, but two 3s do it in two. This… 4 min read · 2 Nov computer-science/binary-search-trees-why-the-order-you-insert-numbers-changes-how-fast.md Binary search trees: why the order you insert numbers changes how fast you can find them A binary search tree keeps numbers in order with one rule: smaller goes left, bigger goes right. Build one yourself, watch a search light… 4 min read · 30 Oct computer-science/merge-sort-how-splitting-a-list-in-half-again-and-again-sorts-it-with.md Merge sort: how splitting a list in half again and again sorts it with far less work How do you sort 10,000 numbers without making millions of comparisons? Merge sort never sorts a big pile. It splits the list until every… 5 min read · 27 Oct computer-science/hash-tables-how-a-computer-finds-one-name-among-thousands-without-chec.md Hash tables: how a computer finds one name among thousands without checking them all Your phone finds one contact among thousands without reading them all. The trick is a hash table: a row of numbered slots and a small… 6 min read · 24 Oct computer-science/stacks-and-queues-why-undo-takes-the-newest-item-and-a-printer-takes-t.md Stacks and queues: why undo takes the newest item and a printer takes the oldest Press undo and the last thing you typed disappears first. Send documents to a shared printer and the first one is printed first. Both are… 5 min read · 20 Oct computer-science/breadth-first-search-how-a-maze-solver-finds-the-shortest-way-out.md Breadth-first search: how a maze solver finds the shortest way out How does a maze solver, or a map app, find the shortest route and not just any route? The answer is breadth-first search: explore every… 6 min read · 17 Oct