Array Layout and the Sift Invariant in Binary Heaps

A binary heap is a complete binary tree with one additional condition: no node’s key exceeds the key of either child. That condition is a partial order, not a total one. It constrains each node only against its own descendants, so a heap of n keys asserts n − 1 relations where a sorted array would fix all n(n−1)/2 pairs. The economy is the entire point. Preserving a total order under insertion costs Θ(n) per element in the worst case, because a new key can belong anywhere. Preserving this partial order costs O(log n), and the three operations a priority queue actually needs — read the minimum, remove it, insert a key — never demand more information than the partial order carries.

A partial order that fits in a flat array

A total order answers every comparison. A heap answers only ancestor-descendant comparisons. Given two sibling subtrees, the heap says nothing about their relative keys, and that silence is deliberate: it is exactly the information the structure declines to maintain. The consequences are worth stating plainly, because they explain both what a heap is good for and the questions it cannot be asked.

• The minimum is at the root, so reading it is O(1) and touches a single slot.
• The second-smallest element is one of the root’s two children, but which one is not recorded.
• An arbitrary key cannot be found faster than by scanning all n slots. There is no search path.
• In-order traversal yields nothing meaningful. A heap has no sorted iteration order.
• Removing the minimum requires restructuring, because the remaining n − 1 keys must satisfy the invariant again with a different root.

The last point is where the array layout pays off. Removing the root would leave a hole at the top of the tree; instead the implementation takes the last occupied slot, moves its key to the root, and repairs the invariant downward. No node moves between levels, no memory is freed, and the tree remains complete after every operation. Completeness is not an aesthetic property — it is what allows the mapping described next.

Index arithmetic replaces every pointer

Number the slots of a complete binary tree level by level, left to right, starting at zero. The root occupies index 0; its children occupy 1 and 2; their children occupy 3 through 6, and so on. In this numbering, for a node at index i:

• children sit at 2i + 1 and 2i + 2,
• the parent sits at (i − 1) / 2 using integer division,
• the last element of a heap holding n keys is at index n − 1.

A one-based numbering, used by some textbooks and by the algorithms literature, shifts the formulas to 2i and 2i + 1 for children and ⌊i/2⌋ for the parent, and the root sits at 1. The two conventions are equivalent; mixing them in one codebase is a reliable source of off-by-one defects, since a one-based 2i on a zero-based array silently reads the wrong node.

Because the tree is complete, the array has no gaps. Every index below n holds a key, every index at or above n is unused, and the shape is determined entirely by n. This eliminates the per-node pointer overhead of a linked tree — commonly two pointers plus a key, so roughly three machine words per element against one — and it makes the structure trivially serialisable: the array is the heap.

The height follows from completeness. A complete tree with n nodes has height ⌊log₂ n⌋, so a heap of a million keys has height 19 and a heap of a billion has height 29. Every operation that walks a root-to-leaf path therefore performs at most 30 steps at the upper end of practical sizes, and the first four levels — 15 nodes — occupy 60 bytes if keys are four bytes each, one cache line on machines whose lines are 64 bytes.

Insertion climbs, extraction descends

Two repair routines maintain the invariant, and they differ in direction because they repair different kinds of damage.

Insertion appends the new key at index n, which is the leftmost free position on the last level, then sifts up: while the key is smaller than its parent, swap the two and continue from the parent’s index. Each swap strictly decreases the key’s depth, so the loop terminates within ⌊log₂ n⌋ iterations. Only one root-to-leaf path is affected, and the rest of the heap is untouched.

Extraction of the minimum replaces the root with the last key and shrinks the array by one, then sifts down: compare the key against both children, swap with the smaller of them, and repeat. The choice of the smaller child is not a heuristic. Promoting the larger child would leave a key below its new parent and violate the invariant immediately, and no amount of further descent repairs it.

/* Min-heap in a[0..n-1]; repairs the subtree rooted at slot i. */
static void sift_down(int *a, size_t n, size_t i) {
    for (;;) {
        size_t l = 2 * i + 1, r = l + 1, m = i;
        if (l < n && a[l] < a[m]) m = l;
        if (r < n && a[r] < a[m]) m = r;   /* pick the smaller child, not either child */
        if (m == i) return;
        size_t t = a[i]; a[i] = a[m]; a[m] = t;   /* index type, not key type */
        i = m;
    }
}

Each level costs two comparisons and one swap in the worst case, so a sift-down is bounded by 2⌊log₂ n⌋ comparisons. The move itself is the expensive part when elements are large: three loads and three stores per level, each potentially a cache miss once the path leaves the top of the array. Implementations that care about constant factors hoist the key into a register and shift elements down instead of swapping, writing each element once rather than three times, and place the key in its final slot at the end.

Insertion is cheap on average, extraction is not

The two repairs are not symmetric in cost, and the asymmetry is not captured by the worst-case bound.

A sift-down must often descend to the bottom of the heap: an element that belongs at a leaf travels the full height, so the cost is Θ(log n) for the operations that matter. A sift-up stops as soon as the new key is no larger than its parent, and for keys arriving in random order it stops almost immediately. If the keys are in random order, a new key rises at least k levels exactly when it is the smallest of the k + 1 keys on that root path, which has probability 1/(k+1). The expected number of rises is the sum of those probabilities,

$$ \sum_{k=1}^{h} \frac{1}{k+1} ;=; H_{h+1} - 1 $$

bounded by the harmonic number of the height h rather than of n. A heap of a million keys has height 19, so the expectation is below H₂₀ − 1 ≈ 2.6 rises.

The consequence is a cost model that differs from the textbook one. A workload of insertions followed by a single drain is dominated by the drain, not by the insertions. A workload that inserts and extracts in alternation pays the full logarithmic cost on every extraction and almost nothing on every insertion. And a workload that inserts keys in decreasing order — which is exactly what a naive priority queue sees when it is fed a sorted list — pays the full height on every insertion, since each new key is the new minimum. The worst case is real; it is simply not the common case.

Where the invariant is weaker than it looks

The heap property says nothing about equal keys, and nothing about the relative order of keys that compare equal. A heap is therefore not stable: two entries with identical priority may be extracted in either order, and the order can differ between two runs of the same program if the comparator is inconsistent. Priority queues that must break ties deterministically attach a monotonically increasing sequence number to each entry and compare on the pair, which restores a total order at the cost of one extra word per element and one extra comparison.

A second edge is the comparator itself. The invariant is only as meaningful as the relation supplied. A comparator that is not a strict weak ordering — one that reports a < b and b < a for the same pair, or that changes its answer over time because it reads mutable state — can leave the array in a state where sift-down loops forever or terminates with the minimum buried. The structure has no way to detect this; it trusts the relation.

Third, the bound is on the height, not on the work per level. For large elements — a 200-byte struct keyed on one integer — moving elements dominates comparison, and an array of pointers to elements, or an index-based heap over a separate key array, is faster than moving the payload. That is one reason standard libraries expose a container adaptor over an arbitrary sequence rather than owning storage.

The same reasoning about per-level cost drives the choice of branching factor. A binary heap pays two comparisons per level over log₂ n levels; a heap whose nodes have d children pays d comparisons over log_d n levels, and the product dips below the binary figure only in the neighbourhood of d = 3. That trade is the subject of d-ary heaps and branching factor. Before any of that matters, though, a heap has to be built from an unordered array, and doing so naively costs more than the structure requires — see bottom-up heap construction.