58The heap — a tree that lives in an array

In Chapter 57 we spent two pointers per node to keep a tree searchable, and fought it on every insert to stay balanced. Here we make the opposite bargain: a tree that spends no pointers at all. A heap is a binary tree with a rule so tight that its shape no longer has to be stored. It folds flat into one contiguous array, and plain arithmetic walks it. Here's the plan. We fold the tree into an array, navigate it by doubling and halving a single index, then add and remove items by letting one value climb or sink along one path. The whole way through, we keep asking the one question that matters — if the tree isn't stored anywhere, what is actually holding its shape? By the end you'll see why the smallest of a million items always sits at index 0, why pulling it out costs only ~20 hops, and why every priority queue, scheduler, and shortest-path frontier you've ever used is this one flat array underneath.

01A whole tree, and not one pointer

Let's start with two terms, each defined the moment it appears. A complete binary tree is filled level by level, top to bottom, and each level left to right. Every level is full except possibly the last, and the last is packed to the left with no gaps. That "no gaps" rule is the whole secret, so hold onto it. The second term is the heap property: in a min-heap, every parent is less than or equal to both of its children. That is not the same as sorted — it just means parent-below-children, everywhere. Two consequences follow right away. First, the smallest value in the whole tree has nobody smaller above it, so it must sit at the root. Second, the arrangement is only a partial order, so the root's two children can sit in any order relative to each other.

Now look at the memory picture, which is this volume's obsession. Back in the binary-tree chapter, a plain binary tree had to store two pointers in every node just to remember where its children live, because the nodes sat at unrelated heap addresses. A complete tree has no gaps. So number its nodes in reading order — root 0, then 1, 2, then 3, 4, 5, 6 — and those numbers are dense: 0, 1, 2, 3, … with nothing missing. Dense integers starting at zero are exactly what an array index is. So drop the values into a flat array in that order, and the tree is gone as a scatter and present as an array. The shape isn't stored anywhere — it's implied by position. That is the human insight this whole chapter rests on.

So how heavy is it? Weightless, by tree standards — but let's measure rather than guess. A heap of n items is one list of n references: about 8 bytes per element of structure, plus one small header. The pointer-based tree node from the binary-tree chapter spent 56 bytes per node just to hold a header and two child pointers. The heap pays none of that.

import sys
heap = [1, 3, 6, 5, 9, 8, 7]          # a heap is just a list
print(sys.getsizeof(heap))            # 120  → header + 7 eight-byte references

big = list(range(100_000))            # 100k-element heap
print(sys.getsizeof(big))             # 800056  → 8.00 bytes/element of structure
print(sys.getsizeof(big) / 100_000)   # 8.00056

Line 3, on CPython 3.12.7: the seven-element heap weighs 120 bytes — a list header plus seven 8-byte slots. Line 6: a 100,000-element heap is 800,056 bytes, which works out to line 7's 8.00 bytes of structure per element. The pointer tree from the binary-tree chapter needed 56 bytes per node, so the same 100,000 nodes cost 5,600,000 bytes — measured, 7× heavier. The heap is the lightest tree there is, because it is the only tree that stores zero shape. (As always, the values themselves are separate objects on the heap — the array holds references, exactly like any Python list.)

It turned into a calculation. When there are no gaps, the address of a child isn't stored — it's computed. →

02The address of a child is a formula

Here is why "no gaps" buys everything. Number the tree in reading order and look at any node at index i. Its two children are the next two nodes laid down after all of i's left-neighbours have filled their own children. Because the tree is complete, that "next two" always lands at fixed offsets. The result is three formulas that never change:

• left child of i is at 2*i + 1
• right child of i is at 2*i + 2
• parent of i is at (i - 1) // 2 (integer division — the two child formulas run backwards)

Check it against the figure. Node [1] holds 3; its children should be at 2·1+1=3 and 2·1+2=4, and indices 3 and 4 do hold 5 and 9 — the two nodes drawn beneath it. Correct. Node [5] holds 8; its parent is at (5-1)//2 = 2, and index 2 holds 6, drawn directly above it. Correct. No search, no pointer dereference: navigating the tree is just doubling and halving an integer. That is O(1) per hop, and it is the cheapest kind of O(1) — a shift and an add, with no memory touched to find the address.

def left(i):   return 2*i + 1
def right(i):  return 2*i + 2
def parent(i): return (i - 1) // 2

h = [1, 3, 6, 5, 9, 8, 7]
print(h[left(1)], h[right(1)])   # 5 9   → the children of node 3
print(h[parent(5)])              # 6     → the parent of node 8

Those three one-liners are the complete navigation system of a heap — no Node class, no .left/.right fields, nothing on the heap but the array. Lines 6–7 ran on CPython 3.12.7 and printed exactly 5 9 and 6, matching the diagram.

We can climb and descend for free. Now use it: to add a value and keep the heap a heap, you only ever walk one path — straight up. →

03Insert = drop it at the end, then let it climb

Adding to a heap has to preserve two things at once: completeness (no gaps) and the heap property (parent ≤ children). Completeness settles where the new value goes. The only spot that keeps the tree gapless is the very next array slot, so we append it to the end. That is O(1) amortized, the list's own trick from Volume 1. But the newcomer may be smaller than its parent, breaking the heap property on that one edge. So we repair it with sift-up (also called bubble-up or percolate-up): compare the new value with its parent; if it's smaller, swap them; then repeat from the new position, until it's no longer smaller than its parent or it reaches the root.

Why is that correct, and why O(log n)? Correct because each swap fixes the only broken edge and can only create a new broken edge one level up — the disorder travels upward and nowhere else. Cheap because it walks a single root-ward path, and the tree's height is ⌊log₂n⌋ (a complete tree is as short as a tree can be). So a heap of a million items is 19 levels tall — an insert touches at most 19 slots. Watch it happen with a real value:

Insert 2 into [1, 3, 6, 5, 9, 8, 7] and this is exactly the trace CPython 3.12.7 produced: 2 is appended at index 7; its parent at (7-1)//2=3 is 5, and 2 < 5, so they swap; its new parent at index 1 is 3, and 2 < 3, so they swap; its next parent at index 0 is 1, and 2 ≥ 1, so it stops. Two swaps, final array [1, 2, 6, 3, 9, 8, 7, 5]. In real code you never hand-roll this — Python's heapq is the heap, operating in place on an ordinary list.

import heapq
h = [1, 3, 6, 5, 9, 8, 7]      # already a valid min-heap
heapq.heappush(h, 2)           # insert 2, sift-up runs internally
print(h)                       # [1, 2, 6, 3, 9, 8, 7, 5]
print(h[0])                    # 1   → the minimum, O(1), always at index 0

heapq.heappush (line 3) does the append-then-sift-up you just watched, in C, in place on the list h. Line 4 printed [1, 2, 6, 3, 9, 8, 7, 5] — the same array the trace produced. And line 5 is the quiet superpower: the minimum is always at h[0], so peeking at it is a single array read, O(1), no matter how many items the heap holds.

Peeking at the minimum is free. But a priority queue has to remove it and hand you the next-smallest — and the root is the one slot you can't just delete without tearing a hole in the tree. →

04Extract-min = promote the last, then let it sink

To remove the minimum you can't simply erase index 0 — that would orphan its two subtrees. The trick mirrors insert. Take the root's value to return it. Now you need to fill the hole at the top and keep the tree complete, and there's exactly one value whose removal keeps it gapless: the last one in the array. So move the last element up to the root, shrinking the array by one. That almost certainly violates the heap property — a leaf value now sits at the top — so repair it downward with sift-down (bubble-down): compare the value with its smaller child; if it's larger, swap with that child; repeat, until it's ≤ both children or reaches a leaf. Comparing against the smaller child is the subtle, essential detail — swap with the larger and you'd just recreate the violation.

That figure is the exact run from CPython 3.12.7: pop 1; move last value 7 to the root; 7 > 3 (the smaller of children 3 and 6) so swap; 7 > 5 (its new smaller child) so swap; now a leaf — stop. Final heap [3, 5, 6, 7, 9, 8], and the new minimum 3 has surfaced at index 0. The whole operation walked one path down, so it is O(log n) — 19 steps for a million items.

import heapq
h = [1, 3, 6, 5, 9, 8, 7]
heapq.heapify(h)               # make sure it obeys the heap property
smallest = heapq.heappop(h)    # remove & return the min; sift-down runs internally
print(smallest)                # 1
print(h)                       # [3, 5, 6, 7, 9, 8]

heappop (line 4) performs the promote-last-then-sift-down you just traced and hands back the minimum. Line 5 printed 1; line 6 printed [3, 5, 6, 7, 9, 8] — matching the figure exactly. Push and pop together give you a priority queue: a bag you throw items into in any order and always draw the smallest (or highest-priority) out, each operation O(log n), the peek free.

Push, pop, peek — the whole priority queue. But there's a faster way in than pushing one at a time. Handing a heap a whole array at once costs less than you'd ever guess. →

05Building a heap in O(n) — the pleasant surprise

You have an array of a million values in random order and you want a heap. The obvious way: start empty and heappush each item — n inserts, O(log n) apiece, so O(n log n) total. But there's a better way, and its cost is a genuine surprise. Heapify works bottom-up, in place: skip the leaves (the second half of the array — they're already valid one-element heaps), and run sift-down on every internal node from the last one back to the root. When you fix a node, its two subtrees are already heaps, so one sift-down settles it.

Now the surprise — and it's worth deriving, because the intuition "n nodes times log n each = O(n log n)" is exactly the trap. That estimate assumes every node sinks the full height. It doesn't. Half the nodes are leaves and do zero work. A quarter sit one level up and sink at most one step. An eighth sink at most two. In general, the many nodes near the bottom have almost no distance to fall, and only the lone root can fall the full ⌊log₂n⌋. Sum the real work — n·(1/2·0 + 1/4·1 + 1/8·2 + 1/16·3 + …) — and the series in parentheses converges to a constant (it's under 1). Total work is proportional to n. Heapify is O(n): you can turn a raw array into a heap in linear time.

import heapq, random
data = [random.randint(0, 10**9) for _ in range(1_000_000)]

# way 1: push one at a time — O(n log n)
h1 = []
for x in data: heapq.heappush(h1, x)

# way 2: heapify the whole array in place — O(n)
h2 = list(data)
heapq.heapify(h2)              # ~2.3x faster here, and the gap widens with n

Timed on this machine (CPython 3.12.7 — timings are machine-dependent): building the million-item heap by repeated heappush took about 65 ms; heapify on the same data took about 28 ms — roughly 2.3× faster, both producing a valid heap with the same minimum. The measured gap here is modest because Python's per-operation overhead dominates, but the asymptotic difference — O(n) versus O(n log n) — only grows as the data does. When you have all the items up front, always reach for heapify.

Peek in O(1), push and pop in O(log n), build in O(n), sort in O(n log n) — all from one flat array. Now the only question left is the one that matters most: when, on sight, is a heap the right container? →

06When to reach for a heap

The heap answers one access pattern, and it answers it better than anything else: "give me the most extreme item, over and over, while items keep arriving." Not "sort everything" — that's a one-shot. Not "look things up by key" — that's what a hash map is for. The heap's home is the running extreme: a set that changes under you, from which you repeatedly pluck the min or max. The instant a problem sounds like "always process the smallest / largest / nearest / highest-priority next," the heap is the answer, and choosing it on sight is most of what "good at data structures" means.

The clean way to feel the win is top-k. To find the 10 largest of a million numbers, you do not sort the million (O(n log n)) — you keep a heap of just 10 and let each new number bump the smallest survivor (O(n log k)).

That "heap of just 10" hides the whole trick. Sorting forces you to hold every number at once so it can rank them; the heap holds only the k survivors and lets each new value either bump the smallest of them or fall away forever. Drag the pile from a thousand up to a billion and watch what the two approaches must keep in memory:

import heapq, random
scores = [random.randint(0, 10**6) for _ in range(1_000_000)]

top10 = heapq.nlargest(10, scores)     # a size-10 heap sweeps the stream once

Measured on this machine: heapq.nlargest(10, scores) over a million values took about 14 ms, against about 149 ms for sorted(scores, reverse=True)[:10] — the same ten numbers, roughly 10× faster, because the heap never pays to order the 999,990 items you were going to throw away. That is the whole art: the heap sorts nothing; it just keeps the boundary.

Finally, the boundary that trips people — heap versus the binary search tree of the last chapter. Both are binary trees; they are opposites in purpose. A BST enforces a total order (left < node < right) so it can find any value and walk everything in sorted order — but it's a pointer structure that must fight to stay balanced. A heap enforces only a partial order (parent ≤ children) so it can find one value — the extreme — and it lives pointerless in an array, always perfectly balanced by construction. Ask "is 42 in here?" and the heap is useless (O(n) — it must scan). Ask "what's the smallest?" and the BST is merely fine while the heap is instant.

That is the 1% move in one line: match the question to the layout. "Any key, in order" → a BST or a hash map. "The extreme, repeatedly, as data streams" → a heap. Recognising which of those two questions a problem is really asking — before you type — is the whole skill; import heapq is the easy part that follows.

Next (chapter 59): we've keyed data by number and by hash, and ordered it by comparison. But some data is made of sequences of symbols — words, IP addresses, DNA — and there's a tree that branches not on "bigger or smaller" but on the next character, turning "find every word starting with str" into a walk of three steps. That's the trie, the structure behind autocomplete, spell-check, and how a router decides where your packet goes next. →