The heap invariant

A heap is an array with one rule: every parent beats both of its children. For a min-heap, "beats" means "is less than or equal to". There is no left-versus-right order, no sorted sequence, and no pointers — the rule is weak enough to restore in about 20 swaps on a million elements, and strong enough that the smallest element always sits at index 0. That trade is the whole data structure; everything below follows from it.

One rule, and everything it does not promise

The invariant constrains each parent against its own two children and says nothing else. In the heap [2, 5, 4, 9, 7, 6], the value 4 sits to the right of 5 and is smaller than it — legal, because they are not parent and child.

So a heap will not answer what a sorted array or a search tree answers. "Is 37 in here?" costs O(n): the invariant gives you no way to rule out a subtree. "Give them to me in order" costs n pops, O(n log n) — that is heapsort, and it is not free. What the heap promises is the minimum in O(1) and a repair after any single change in O(log n). When a problem only ever asks for the extreme element, paying for a full ordering is waste — the kind the solving loop tells you to name before you pick a tool.

The second half of the definition is the shape: a heap is a complete binary tree, every level full except the last, which fills left to right. The ordering rule does not require that; completeness is what lets an array hold the tree with no gaps.

The array is the tree

Number the nodes level by level, left to right, and the numbering has arithmetic in it.

A six-element min-heap shown as a tree and as the flat array that holds it, with the child index arithmetic100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

For a node at index i:

left   = 2 * i + 1
right  = 2 * i + 2
parent = (i - 1) // 2

This is not only tidy. A million 64-bit values is an 8 MB array walked by multiplication rather than by pointer-chasing, and the top 12 levels hold 2¹² − 1 = 4,095 entries — about 33 KB, so they stay in cache. Assume those cost on the order of a 1 ns L1 reference and only the bottom few pay the 100 ns main-memory price: a full 20-level sift is order of 1 µs, against 100 µs for one SSD random read.

Push is a sift-up

Append the new value at the end of the array — the only slot that keeps the tree complete — then walk it up while it beats its parent.

def push(h, x):
    h.append(x)
    i = len(h) - 1
    while i > 0:
        p = (i - 1) // 2
        if h[p] <= h[i]:
            break
        h[p], h[i] = h[i], h[p]
        i = p

Each iteration halves the index, so the loop runs at most ⌊log₂ n⌋ times. At n = 1,000,000 that is ⌊log₂(10⁶)⌋ = 19: at most 19 comparisons and 19 swaps. The round 20 only arrives at n = 2²⁰ = 1,048,576, the size used below. The break matters in practice — a value pushed into a random heap usually stops after a step or two.

Pop is a sift-down

Removing the minimum is the same move in reverse. You cannot delete index 0 outright; that leaves a hole. Move the last element into the root, shrink the array by one, then walk that element down, always swapping with the smaller child — swap with the other one and the invariant breaks on the side you ignored.

def pop(h):
    top = h[0]
    last = h.pop()
    if h:
        h[0] = last
        i, n = 0, len(h)
        while True:
            c = 2 * i + 1
            if c >= n:
                break
            if c + 1 < n and h[c + 1] < h[c]:
                c += 1          # the smaller child, not the left one
            if h[i] <= h[c]:
                break
            h[i], h[c] = h[c], h[i]
            i = c
    return top

Same height bound, two comparisons per level instead of one: about 40 at a million elements. Unlike push, sift-down rarely stops early — the value you moved to the root came from the bottom, so it is usually large and usually falls most of the way back. That asymmetry is what makes the next section work.

Peek is h[0], O(1). That one line is what every pattern in top-k and two heaps is buying.

Building from n items is O(n), not O(n log n)

The obvious build is n pushes, which is O(n log n) in the worst case — up to 1,048,576 × 20 ≈ 21 million comparisons for a heap of 2²⁰ items. That bound is loose in both directions: descending input, the true worst case, sends every value to the root for 18.9 million comparisons, while random input costs about 2.4 million — roughly 2.3n, because the break above usually fires within a step or two. The better build takes the raw array and sifts down every non-leaf, from the last one backwards to the root. Count what that costs level by level, the way complexity by counting does it.

Half the nodes are leaves, and a leaf sifts down zero levels. A node one level up sifts at most one. In general about n/2^(h+1) nodes sit at height h, and each does at most h swaps:

Height	Nodes (n = 1,048,576)	Swaps each	Total
0	524,288	0	0
1	262,144	1	262,144
2	131,072	2	262,144
3	65,536	3	196,608
4	32,768	4	131,072
…	…	…	…
20	1	20	20

That column sums to 1,048,575 — under n = 1,048,576, by exactly one. The closed form says the same thing: the sum of h/2^(h+1) over all heights converges to 1, so the total stays bounded by n.

A guaranteed n, against a bound that degrades to n log n. The win is not a 20× speedup on typical data — on random input n pushes costs about 2.4 million comparisons, so the gap there is small. What heapify buys is the absence of a bad case: hand the push build sorted-descending data and it pays 18.9 million, while heapify cannot notice the order of its input at all. The reason fits in one sentence: most nodes are near the bottom, and the nodes near the bottom have almost nowhere to fall. The expensive sifts exist; there are only a handful of them. In Python this is heapq.heapify(a), in place.

Python ships one heap, and it is a min-heap

heapq works on a plain list: heappush, heappop, heapify, plus two fused operations — heappushpop (push then pop) and heapreplace (pop then push, on a non-empty heap). Both cost one sift instead of two.

There is no max-heap, so you invert the key:

import heapq

heapq.heappush(h, -x)                       # negate in, negate out
top = -heapq.heappop(h)

heapq.heappush(h, (-score, tie, payload))   # or negate the key in a tuple

Negation fails on anything you cannot negate — strings, dates — where you map to a numeric key or wrap the item in a class with __lt__ reversed.

The tuple form has a trap. Python compares tuples element by element, so on a tie in the first field it compares the second; if that is a dict or an object with no ordering, it raises TypeError — on the tie, not on the first push, which is why it survives your two-item test and dies on real data. Put a unique increasing integer in the middle and the comparison never reaches the payload.

In an interview

The question behind "explain a heap" is whether you know what it costs and what it refuses to do. Lead with the invariant and the two operations, then volunteer the boundary: "peek is O(1), push and pop are O(log n), search is O(n) — if I need membership or ordering, I want a different structure." Then say the build cost, because it is the number most candidates get wrong: "heapify is O(n), since half the nodes are leaves that move zero levels, so I heapify rather than push n times."

The mistake that loses points: sifting down into the left child without checking which child is smaller. It passes every example where the children happen to be in order and silently corrupts the heap otherwise. Write the "pick the smaller child" line first and say why it is there.

The second is calling a heap sorted. [2, 5, 4, 9, 7, 6] is a valid heap and is not sorted; a sorted array is a valid heap, but not the reverse.

Check yourself

A heap holds 1,000,000 elements. You push a value smaller than all of them. How many swaps, and why?

Nineteen — ⌊log₂ 10⁶⌋ = 19. The new value starts at the last index and beats every parent up to the root, so this is push's worst case: one swap per level of height.

You need the 5 smallest of 10 million numbers, once. Heapify then pop five times, or push all 10 million and pop five times?

Heapify: about 10 million operations to build, plus 5 × log₂(10⁷) ≈ 115 for the pops. Pushing all of them is 10 million × 23 ≈ 230 million for the same answer. If the data is a stream too large for memory, neither applies — that is the size-k heap in top-k and two heaps.

You want a max-heap of priority-and-task pairs, where the task is a dict. What breaks, and when?

Negating gives (-priority, task), which works until two tasks share a priority. Python then compares the dicts, which have no ordering, and raises TypeError — at run time, on real data. Push (-priority, counter, task) with a monotonically increasing counter so the comparison resolves before it reaches the dict.