58The heap — a tree that lives in an array

In Chapter 57 we spent two pointers per node to keep a tree searchable. We also fought that tree on every insert to keep it balanced. Here we strike 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 needs storing. It folds flat into one contiguous array, and pure arithmetic walks it. Here's the plan. We'll fold the tree into an array, then navigate it by doubling and halving a single index. After that we add and remove items by letting one value climb or sink along a single path. And the whole way through we keep asking the one thing 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. You'll see why pulling it out costs only ~20 hops. And you'll see 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 words, each defined the moment it lands. A complete binary tree is filled level by level, top to bottom, and each level runs 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 word is the heap property. In a min-heap, every parent is less than or equal to both of its children. That is not sorted. It is just parent-below-children, everywhere. Two consequences fall straight out. The smallest value in the whole tree has nobody smaller above it, so it must sit at the root. And the arrangement is only a partial order, so the root's two children can sit in either order relative to each other.

Let's make that concrete before it stays abstract. Take [1, 3, 6, 5, 9, 8, 7], the heap we'll use all chapter. The root is 1, the smallest value, exactly where the rule forces it. Its children are 3 and 6, both larger — good. Node 3's children are 5 and 9, both larger than 3 — good again. Notice what is not required. The 6 sits to the right of 3, yet 6 is bigger than 3. Siblings never have to be ordered, and whole subtrees never have to be ordered against each other. Only the parent-child edge is ever checked. Flip the rule to parent ≥ children and you get a max-heap, with the largest value at the root. Everything in this chapter works the same way, just mirrored.

Now watch the memory picture, this volume's obsession. Back in the binary-tree chapter, a plain binary tree stored two pointers in every node just to remember where its children live. It had to, 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. 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.

It's worth seeing why the no-gaps rule can't bend. Imagine the last level had a hole — say index 4 was empty but index 5 was filled. Then the value we're calling "node 5" isn't really the sixth node in reading order anymore, and its index no longer tells us where its parent sits. The position-to-shape link snaps, and every formula in the next section returns the wrong slot. So completeness isn't a nicety we'd merely like to keep. It is the load-bearing wall: the single promise that lets a position stand in for a stored pointer. That is why every heap operation is built to preserve it.

So how heavy is it? Weightless, by tree standards — but measure, don't guess. A heap of n items is one list of n references. That costs 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. That is a list header plus seven 8-byte slots. Line 6: a 100,000-element heap is 800,056 bytes, which is line 7's 8.00 bytes of structure per element. The pointer tree needed 56 bytes per node for the same 100,000 nodes. That is 5,600,000 bytes, measured, and 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 to be laid down after all of i's left-neighbours filled their children — and because the tree is complete, "next two" 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, so its children should be at 2·1+1=3 and 2·1+2=4. Indices 3 and 4 hold 5 and 9, the two nodes drawn beneath it. Correct. Node [5] holds 8, so its parent is at (5-1)//2 = 2. Index 2 holds 6, drawn directly above it. Correct. There is no search and 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.

Where does 2i+1 actually come from? Count the tree level by level. Level 0 holds 1 node, level 1 holds 2, and level 2 holds 4 — each level doubles, because every node above spawns two below with no gaps between them. So the nodes sitting before i, plus i itself, each contribute two children packed tightly to the left. Do that bookkeeping and the left child of i always lands at 2i+1, with the right child one slot later at 2i+2. Test the smallest case. The root is i=0, so its children are at 1 and 2, the first two slots after it. The doubling in the tree is the doubling in the formula.

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. There is no Node class and no .left/.right fields — there is 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 pins down 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, which breaks the heap property on that one edge. So we repair it by sift-up, also called bubble-up or percolate-up. Compare the new value with its parent. If it's smaller, swap the two. 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)? It is 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. It is 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, which means 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 again. Its next parent at index 0 is 1, and 2 ≥ 1, so it stops. Two swaps, and the final array is [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. That is O(1), no matter how many items the heap holds.

One caveat that trips everyone the first time: Python's heapq is a min-heap only. There is no max flag to set. When you need the largest value out each time, the standard trick is to negate on the way in: push -x instead of x, and negate again when you pop. The smallest of the negatives is the largest of the originals, so -heappop(h) hands back the true maximum. Push -5, -1, -8 and the heap's root is -8, so the first pop returns 8. It feels like a hack, but it's the idiom you'll meet in real code everywhere.

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 so you can return it. Now you need to fill the hole at the top and keep the tree complete. Exactly one value can be removed without leaving a gap: the last one in the array. So move that last element up to the root, shrinking the array by one. It almost certainly violates the heap property now, because a leaf value sits at the top. So repair it downward with sift-down, also called bubble-down. Compare the value with its smaller child. If it's larger, swap with that child. Repeat until it's ≤ both children, or it reaches a leaf. Comparing against the smaller child is the subtle, essential detail. Swap with the larger one, and you'd just recreate the violation.

Here is the smaller-child rule made concrete, because it's the single most common heap bug. Suppose 7 has just been promoted to the top, over children 3 and 6. Swap 7 with the larger child, 6, and now 6 sits above 3 — but 6 is bigger than 3, so the parent-child edge is broken all over again. Swap 7 with the smaller child, 3, instead, and 3 rises above 6, which it's already smaller than. The smaller child is the only one guaranteed to be ≤ its new sibling, so it's the only safe value to lift. Pick it, and the violation moves strictly downward until it runs out of tree.

That figure is the exact run from CPython 3.12.7. Pop 1, then move last value 7 to the root. Now 7 > 3, the smaller of children 3 and 6, so swap. Then 7 > 5, its new smaller child, so swap again. It is a leaf now, so stop. The final heap is [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, and line 6 printed [3, 5, 6, 7, 9, 8], matching the figure exactly. Push and pop together give you a priority queue. It is a bag you throw items into in any order, and always draw the smallest or highest-priority one out. Each operation is O(log n), and the peek is free.

That one shape — throw items in, always pull the most urgent out — is quietly everywhere. Dijkstra's shortest-path algorithm keeps a heap of frontier nodes and repeatedly pops the closest one, and that pop is the heart of the routing in your maps app. An operating-system scheduler keeps runnable threads in a priority structure and pops the highest-priority one to run next. A discrete-event simulator keeps future events keyed by timestamp and pops whichever happens soonest. None of these ever needs the whole set sorted. They need the next extreme, now, over and over — which is precisely the one thing a heap does in O(log n).

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 is to start empty and heappush each item. That is n inserts at 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, which are already valid one-element heaps. Then 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.

Why is "the second half" exactly the leaves? A node is a leaf when it has no children, and node i's first child would sit at 2i+1. So i is a leaf the moment 2i+1 runs past the end of the array. Work that out and every index from n//2 onward is a leaf. For our seven-element heap, 7//2 = 3, so indices 3, 4, 5, 6 — the last four — are leaves, and only 0, 1, 2 are internal nodes worth sifting. Half the array does zero work, which is the first hint that heapify is cheaper than it looks.

Now the surprise, and it's worth deriving, because one intuition is exactly the trap. That intuition says "n nodes times log n each = O(n log n)". It assumes every node sinks the full height, and 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. 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, under 1. So 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, and 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, and both produced 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.

INPUTimport heapq

# (urgency, minutes past 14:00, patient) - 1 = resuscitate now, 5 = can wait
waiting = [
    (3,   0, "you - sprained wrist"),
    (4,  15, "sore throat"),
    (1, 120, "chest pain"),
    (2,  35, "deep cut, bleeding"),
    (3,   8, "twisted ankle"),
    (5,   5, "repeat prescription"),
]

room = list(waiting)
heapq.heapify(room)                 # O(n) - the whole room in one pass
print("the array after heapify:")
for slot, p in enumerate(room):
    print(f"  [{slot}] {p}")
print("who is next:", room[0], "  <- O(1) peek, no scan")

print("\ntreatment order:")
order = list(room)
while order:
    urgency, arrived, who = heapq.heappop(order)
    print(f"  urgency {urgency}  arrived +{arrived:3} min  {who}")

heapq.heappush(room, (1, 140, "stroke symptoms"))   # a walk-in, mid-shift
print("\nafter one push, next is:", room[0])
print("three most urgent      :", [p[2] for p in heapq.nsmallest(3, waiting)])
print("least urgent           :", [p[2] for p in heapq.nlargest(1, waiting)])
print("heappushpop (burn)     :", heapq.heappushpop(room, (2, 200, "burn"))[2])

OUTPUTthe array after heapify:
  [0] (1, 120, 'chest pain')
  [1] (2, 35, 'deep cut, bleeding')
  [2] (3, 0, 'you - sprained wrist')
  [3] (4, 15, 'sore throat')
  [4] (3, 8, 'twisted ankle')
  [5] (5, 5, 'repeat prescription')
who is next: (1, 120, 'chest pain')   <- O(1) peek, no scan

treatment order:
  urgency 1  arrived +120 min  chest pain
  urgency 2  arrived + 35 min  deep cut, bleeding
  urgency 3  arrived +  0 min  you - sprained wrist
  urgency 3  arrived +  8 min  twisted ankle
  urgency 4  arrived + 15 min  sore throat
  urgency 5  arrived +  5 min  repeat prescription

after one push, next is: (1, 120, 'chest pain')
three most urgent      : ['chest pain', 'deep cut, bleeding', 'you - sprained wrist']
least urgent           : ['repeat prescription']
heappushpop (burn)     : chest pain

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 that pattern 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. It is 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, or highest-priority next," the heap is the answer. 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, which is O(n log n). You keep a heap of just 10, and let each new number bump the smallest survivor. That is 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. Each new value either bumps the smallest of them, or falls 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. That is against about 149 ms for sorted(scores, reverse=True)[:10]. 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, but 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. The cost is that 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. In return it lives pointerless in an array, always perfectly balanced by construction. Ask "is 42 in here?" and the heap is useless — O(n), because 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" points to a BST or a hash map. "The extreme, repeatedly, as data streams" points to 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.

import heapq, itertools

# (minute the event happens, urgency, patient) - one night, one triage nurse
events = [
    (  0, 3, "you - sprained wrist"),
    (  5, 5, "repeat prescription"),
    (  8, 3, "twisted ankle"),
    ( 15, 4, "sore throat"),
    ( 35, 2, "deep cut, bleeding"),
    ( 40, 1, "sore throat"),        # RE-TRIAGE: the throat turns out to be an airway
    (120, 1, "chest pain"),
]

def treatment_order(events, minutes_each=20):
    room, seq = [], itertools.count()
    live = {}                                   # patient -> the urgency we trust
    log, clock, i = [], 0, 0
    events = sorted(events)
    while i < len(events) or room:
        while i < len(events) and events[i][0] <= clock:      # everyone in by now
            minute, urgency, who = events[i]; i += 1
            live[who] = urgency
            heapq.heappush(room, (urgency, minute, next(seq), who))
        if not room:                            # empty room: wait for the door
            clock = events[i][0]; continue
        urgency, arrived, _, who = heapq.heappop(room)
        if live.get(who) != urgency:            # a stale copy - skip it
            continue
        log.append((clock, urgency, arrived, who))
        del live[who]
        clock += minutes_each
    return log

print("treatment order:")
for called, urgency, arrived, who in treatment_order(events):
    print(f"  called at t={called:3}   urgency {urgency}   logged +{arrived:3}   {who}")

print("\nthe tie, on purpose - two patients at urgency 3:")
tie = []
for urgency, arrived, who in [(3, 8, "twisted ankle"), (3, 0, "you - sprained wrist")]:
    heapq.heappush(tie, (urgency, arrived, who))
print("  pop order:", [heapq.heappop(tie)[2] for _ in range(2)])

# ---------------- OUTPUT, verbatim (CPython 3.12.7) ----------------
# treatment order:
#   called at t=  0   urgency 3   logged +  0   you - sprained wrist
#   called at t= 20   urgency 3   logged +  8   twisted ankle
#   called at t= 40   urgency 1   logged + 40   sore throat
#   called at t= 60   urgency 2   logged + 35   deep cut, bleeding
#   called at t= 80   urgency 5   logged +  5   repeat prescription
#   called at t=120   urgency 1   logged +120   chest pain
#
# the tie, on purpose - two patients at urgency 3:
#   pop order: ['you - sprained wrist', 'twisted ankle']

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. →