A Heap Is a Tree You Can Store in a Flat Array

✓ numbers produced by the code on this page · Published 2026-08-20

A binary heap makes one promise and it is a weak one: a parent is never larger than its children. That is all. The values are not sorted, siblings are in no particular order, and knowing where a value sits tells you almost nothing about the rest.

That weakness is the design. Sorting an array to find the smallest value costs far more than necessary, because you asked for one fact and paid for all of them. A heap keeps the least it can get away with while still putting the smallest value somewhere you can reach instantly.

One value, one path

Insert a few values, then remove the minimum a few times. Press Step to advance the sift one swap at a time.

Sift a heap one value, one path, never across

A binary min-heap keeps the smallest value at the root, and keeps only one promise about everything else: a parent is never larger than its children. That is far weaker than being sorted, and it is exactly enough to make "give me the smallest" instant.

It is stored as a plain array. The children of index i live at 2i + 1 and 2i + 2, and its parent at (i - 1) // 2, so the tree needs no pointers at all. Inserting 8, 3, 12, 1, 9, 5, 14, 2, 7 one at a time produces the array 1, 2, 5, 3, 9, 12, 14, 8, 7 — 4 levels deep — after 6 swaps, because each new value only ever travels one path from its leaf toward the root.

That path-shaped cost is the whole point. Building a 63-value heap by inserting values one at a time costs 258 swaps; building it from the same values with bottom-up heapify costs 57.

The highlighted cells are the ones being compared. Watch them move in the tree and in the array at the same moment — it is one structure being shown twice, not two structures kept in step.

Two things are worth pausing on.

The array is not an implementation detail. The tree has no pointers anywhere. A node’s children are at 2i + 1 and 2i + 2, its parent at (i - 1) // 2, and those formulas are the entire connection between the picture and the memory. Heaps are usually taught as trees and then implemented as arrays, and the join between the two is left as three formulas to memorise — which is why so many people can draw a heap and not write one.

A value never moves sideways. Whether it is sifting up after an insert or down after a removal, it swaps along a single path between root and leaf. That is why an operation costs the height rather than the size: at 1023 values the tree is 10 levels deep, so a swap chain is at most 10 long, not 1023.

Removing the minimum is the clever part

Taking the root is easy. The interesting question is what replaces it, and the answer looks wrong at first: the last element in the array moves to the root, and then sifts down.

Using the last element rather than the smaller child means only one value moves into the gap instead of a cascade rippling up, and the array stays gap-free so the index arithmetic still holds. The newly promoted value is almost certainly in the wrong place, so it sinks — again along one path.

Keep removing the root and the values come out smallest-first. That is heapsort, and it is worth noticing what just happened: a structure that never sorted anything handed back a sorted sequence, purely by being asked for the minimum repeatedly.

Building a heap: the surprising part

The obvious way to build a heap from a pile of values is to insert them one at a time. The better way is to dump them into the array in any order and then sift down from the middle backwards. Both produce a valid heap. They do not cost the same.

def sift_up(heap, i):
    """Move heap[i] up while it is smaller than its parent. Returns the swaps it took."""
    swaps = 0
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] >= heap[parent]:
            break
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent
        swaps += 1
    return swaps


def sift_down(heap, i):
    """Move heap[i] down while a child is smaller. Returns the swaps it took."""
    swaps = 0
    n = len(heap)
    while True:
        smallest, left, right = i, 2 * i + 1, 2 * i + 2
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            return swaps
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest
        swaps += 1


def build_by_inserting(values):
    heap, swaps = [], 0
    for v in values:
        heap.append(v)
        swaps += sift_up(heap, len(heap) - 1)
    return heap, swaps


def build_by_heapify(values):
    heap, swaps = list(values), 0
    for i in range(len(heap) // 2 - 1, -1, -1):
        swaps += sift_down(heap, i)
    return heap, swaps


def is_min_heap(heap):
    return all(heap[i] >= heap[(i - 1) // 2] for i in range(1, len(heap)))


print(f"{'values':>7}  {'by inserting':>12}  {'by heapify':>10}  {'both valid':>10}")
for n in (15, 63, 255, 1023):
    worst = list(range(n, 0, -1))          # reverse order: every insert sifts all the way up
    a, insert_swaps = build_by_inserting(worst)
    b, heapify_swaps = build_by_heapify(worst)
    ok = is_min_heap(a) and is_min_heap(b)
    print(f"{n:>7}  {insert_swaps:>12,}  {heapify_swaps:>10,}  {str(ok):>10}")

Output

 values  by inserting  by heapify  both valid
     15            34          11        True
     63           258          57        True
    255         1,538         247        True
   1023         8,194       1,013        True

Your output

Look at the last row. Heapify used 1,013 swaps to arrange 1,023 values — fewer swaps than there are values. Inserting one at a time used 8,194, which is roughly 1023 × 8, the shape of n log n.

The reason is a counting argument that is easy to state and easy to disbelieve. Inserting sifts up, and half of all the nodes are leaves — the ones furthest from the root, with the longest possible climb. Heapify sifts down, and starts at the halfway point, so the half of the array that is leaves is skipped entirely and does no work at all. The nodes that can travel furthest are the ones there are fewest of. Sum it up and the total is linear in n, not n log n.

Both columns produce a valid heap — the last column checks that on every row, because a cheaper build that produced a broken heap would not be cheaper, it would be wrong.

What this page simplifies

Min-heap only. A max-heap is the identical structure with the comparison flipped. Nothing else changes.
Swaps, not seconds. Swap counts are deterministic and identical on any machine. Real timing would favour heapify by a further margin, since it touches memory in a more cache-friendly order.
Reverse-sorted input. That is the worst case for insertion-building, chosen to make the gap clearest. On random input insertion-building is cheaper than shown here — and heapify still wins.
No decrease-key. Real priority queues often need to change a key’s priority after inserting it, which needs a way to find a value’s index. That is a genuine complication and is left out.
Removal only from the root. Deleting an arbitrary value from a heap is possible but is not what heaps are for; if you need that, you probably want a different structure.

Lists: Your First Collection — python · foundations
for Loops and range() — python · foundations
Writing Your Own Functions — python · foundations

A Heap Is a Tree You Can Store in a Flat Array

One value, one path

The same heap, as values

Removing the minimum is the clever part

Building a heap: the surprising part

What this page simplifies

Learn this properly