Binary Heaps

A binary heap is a data structure representing a nearly complete binary tree — every level is full except possibly the last, which is filled left to right — stored in a plain array with no explicit child or parent links. The tree structure is implicit: the position of an element in the array alone determines its parent and children via arithmetic. Using 0-based indexing, for a node at index $i$: ``` parent(i) = ⌊(i - 1) / 2⌋ left(i) = 2i + 1 right(i) = 2i + 2 ``` This works because a nearly complete tree, read level by level (a level-order traversal), produces exactly the sequence of array slots $0, 1, 2, \ldots, n-1$ with no gaps — the defining structural guarantee that makes the arithmetic valid. The second ingredient is the heap property (also called the heap invariant). In a max-heap, every node's key is greater than or equal to its children's keys:

A min-heap reverses the inequality. The heap property is local — it only constrains parent–child pairs — yet it has a powerful global consequence: the maximum (min-heap: minimum) element of the entire tree always sits at the root, index 0. Note that a heap is not a sorted structure; siblings and distant relatives have no ordering constraint between them at all, which is precisely what makes heap operations cheaper than full sorting. Because the tree is balanced by construction (nearly complete), it has height $h = \lfloor \log_2 n \rfloor$. Every core operation — inserting an element, removing the extreme element, or repairing a single violation — touches at most one root-to-leaf path, giving $O(\log n)$ per operation. This connects heaps to Balanced Binary Search Trees in spirit (both exploit logarithmic height) but heaps achieve it with none of the rebalancing machinery, because they only need a much weaker ordering guarantee.

Sift-up (used after appending a new element at the end of the array) walks the new element toward the root, swapping with its parent as long as the heap property is violated: ``` SIFT-UP(A, i): while i > 0 and A[parent(i)] < A[i]: swap(A[parent(i)], A[i]) i = parent(i) ```

Sift-down (used after replacing the root, typically during extraction) walks an element toward the leaves, swapping with its larger child until no violation remains: ``` SIFT-DOWN(A, i, heap_size): while true: l = left(i) r = right(i) largest = i if l < heap_size and A[l] > A[largest]: largest = l if r < heap_size and A[r] > A[largest]: largest = r if largest == i: break swap(A[i], A[largest]) i = largest ```

Insert appends the new key at the end (preserving the shape property automatically, since the next open array slot is always the correct next tree position) and then sifts it up: ``` INSERT(A, heap_size, key): A[heap_size] = key heap_size = heap_size + 1 SIFT-UP(A, heap_size - 1) ```

Extract-max removes the root, patches the hole by moving the last element into position 0 (again preserving shape), and sifts down to fix the single violation this creates: ``` EXTRACT-MAX(A, heap_size): if heap_size == 0: error "heap is empty" max = A[0] A[0] = A[heap_size - 1] heap_size = heap_size - 1 SIFT-DOWN(A, 0, heap_size) return max ```

Build-heap converts an arbitrary array into a valid heap by calling sift-down on every internal node, working from the last internal node up to the root — critically, in reverse level order, not forward: ``` BUILD-MAX-HEAP(A, n): for i = ⌊n/2⌋ - 1 downto 0: SIFT-DOWN(A, i, n) ``` The loop starts at $\lfloor n/2 \rfloor - 1$ because every index from $\lfloor n/2 \rfloor$ to $n-1$ is a leaf (it has no children within the array bounds), and leaves trivially satisfy the heap property alone. Processing bottom-up ensures that by the time `SIFT-DOWN` is called on node $i$, both of its subtrees are already valid heaps — an invariant argued formally below.

Height and per-operation cost. A nearly complete binary tree on $n$ nodes has height $h = \lfloor \log_2 n \rfloor$: each level except possibly the last is full, so the tree cannot be shallower without violating completeness, and it cannot be deeper without more than one incomplete level. Both `SIFT-UP` and `SIFT-DOWN` follow a single root-to-leaf (or leaf-to-root) path, doing $O(1)$ work per level, so each costs $O(\log n)$ in the worst case. `INSERT` and `EXTRACT-MAX` each do $O(1)$ extra work plus one sift, so they are $O(\log n)$ as well. `FIND-MAX` (peek at index 0) is $O(1)$.

Correctness of sift-down (invariant argument). Consider `SIFT-DOWN(A, i, n)` called when both subtrees rooted at `left(i)` and `right(i)` are already valid max-heaps, but `A[i]` may be smaller than one of its children. The loop's invariant is: at the top of each iteration, the subtree rooted at the current `i` would be a valid heap if `A[i]` were replaced by any value at least as large as `max(A[left(i)], A[right(i)])`. Each iteration identifies the largest of `A[i]` and its children; if `A[i]` is already largest, the local heap property holds and, since both subtrees are already valid, the whole subtree at `i` is valid — the loop correctly terminates. Otherwise it swaps the offending value down into the larger child's slot, which fixes the violation at `i` (the new `A[i]` is the true maximum of the three) while pushing the smaller original root value one level down, where the invariant is re-established for the next iteration. Since each iteration strictly decreases the number of levels remaining below `i`, the loop terminates within $h$ iterations, at a leaf at the latest.

Correctness of build-heap. `BUILD-MAX-HEAP` processes indices $\lfloor n/2 \rfloor - 1, \ldots, 1, 0$ — that is, in decreasing index order. The loop invariant is: at the start of the iteration processing index $i$, every node with index greater than $i$ is the root of a valid max-heap. This holds initially (vacuously, and because all indices $\ge \lfloor n/2 \rfloor$ are leaves, each trivially a size-1 heap). When the loop reaches index $i$, both `left(i)` and `right(i)` exceed $i$, so by the invariant their subtrees are already valid heaps — exactly the precondition `SIFT-DOWN` needs. After the call, the subtree rooted at $i$ is also a valid heap, restoring the invariant with $i$ decremented. When the loop exits (after processing $i = 0$), the entire array is a valid max-heap.

The $O(n)$ build-heap bound. A naive bound charges each of the $\approx n/2$ sift-down calls its worst case $O(\log n)$, giving $O(n \log n)$ — correct but not tight. The precise argument: a node at height $k$ (leaves have height 0) can sift down at most $k$ levels, and there are at most $\lceil n / 2^{k+1} \rceil$ nodes at height $k$ in a heap of $n$ elements. Total work is bounded by

The series $\sum_{k=0}^{\infty} k / 2^k$ converges to $2$ (a standard arithmetico-geometric sum), so the whole expression is $O(n)$. Intuitively: most nodes live near the bottom of the tree (half the nodes are leaves, a quarter are one level up, and so on), and nodes near the bottom can only sift down a few levels — the geometric decay in "how many nodes at height $k$" beats the linear growth in "how far they can move," producing a linear, not linearithmic, total.

Space. A binary heap needs $O(1)$ auxiliary space beyond the array — no pointers, no per-node overhead — which is part of why heaps outperform pointer-based priority queue implementations in practice despite equal asymptotic time bounds. This is the same array, in place; `BUILD-MAX-HEAP` and `EXTRACT-MAX` both operate destructively on the input array, which is exactly what Heapsort exploits to sort in place.

Honest tradeoffs. A heap gives fast access only to the extreme element — searching for an arbitrary key is $O(n)$, unlike a balanced BST's $O(\log n)$. Merging two heaps is $O(n)$ for the standard array-based heap (specialized structures like binomial or Fibonacci heaps trade simplicity for faster merge/decrease-key). And a heap provides no in-order traversal — it is not a substitute for a sorted array when the full order matters.

Build a max-heap from the unsorted array `A = [4, 10, 3, 5, 1, 15, 8]` (indices 0–6, $n = 7$). First, $\lfloor n/2 \rfloor - 1 = \lfloor 7/2 \rfloor - 1 = 2$, so the loop runs for $i = 2, 1, 0$.

The final array `[15, 10, 8, 5, 1, 3, 4]` is a valid max-heap: check every parent–child pair — `15 ≥ 10`, `15 ≥ 8` (root vs. children at 1, 2); `10 ≥ 5`, `10 ≥ 1` (node 1 vs. children at 3, 4); `8 ≥ 3`, `8 ≥ 4` (node 2 vs. children at 5, 6). All hold, confirming the invariant argued above. Now trace `EXTRACT-MAX` on this heap: 1. `max = A[0] = 15`. 2. Move last element to root: `A[0] = A[6] = 4`; shrink `heap_size` from 7 to 6. Array (logical heap): `[4, 10, 8, 5, 1, 3]`. 3. `SIFT-DOWN(A, 0, 6)`: root `A[0]=4`, children `A[1]=10`, `A[2]=8`; largest is 10 at index 1; swap → `[10, 4, 8, 5, 1, 3]`. 4. Continue at `i=1`: `A[1]=4`, children `A[3]=5`, `A[4]=1`; largest is 5 at index 3; swap → `[10, 5, 8, 4, 1, 3]`. 5. Continue at `i=3`: index 3 has no children within `heap_size=6` (`left(3)=7 ≥ 6`); loop stops. Result: `max = 15` is returned, and the remaining heap `[10, 5, 8, 4, 1, 3]` is valid — a second extraction would correctly return `10`.

The binary heap was introduced as the backbone of an elegant in-place sorting algorithm, but its real legacy is the priority queue abstraction it makes efficient. J. W. J. Williams first described the array-based heap and Heapsort in 1964, in a short Communications of the ACM algorithm note — remarkably, in the same year that Robert Floyd published an improved, more efficient version of the build-heap procedure, the same bottom-up construction taught here. The heap concept was then generalized far beyond arrays: binomial heaps, Fibonacci heaps, and pairing heaps each relax the shape or invariant to optimize different operation mixes, feeding directly into faster implementations of Dijkstra's and Prim's graph algorithms.

Priority queues built on binary heaps are the default choice inside Dijkstra's Algorithm and Prim's minimum spanning tree algorithm, where the "extract the closest unvisited vertex" step is exactly `EXTRACT-MAX` (or its min-heap twin) repeated across the graph. Operating system schedulers use heap-based priority queues to pick the next process or timer event to run. Discrete-event simulators — used in network modeling, manufacturing systems, and game engines — rely on a heap keyed by event time to always process the next event in chronological order. Standard library priority queues (C++'s `std::priority_queue`, Java's `PriorityQueue`, Python's `heapq`) are direct implementations of the array-based binary heap described here. And Heapsort itself, while rarely the fastest sort in practice compared to well-tuned quicksort or mergesort variants, remains valuable whenever a guaranteed $O(n \log n)$ worst case and strictly in-place $O(1)$ extra space are both required simultaneously — a combination few other comparison sorts offer. Understanding heaps also clarifies the tradeoffs behind more advanced structures like Fibonacci Heaps, which sacrifice heap simplicity for amortized speedups on decrease-key-heavy workloads.

Ask the tutor: Can you show me how a min-heap's sift-up and sift-down pseudocode differ from the max-heap versions given here?