The Binary Heap

A binary heap is a complete binary tree: every level is full except the last, which fills from the left. Completeness makes the shape a function of the element count alone, so the tree needs no pointers. The nodes are written into an array in level order.

For the node at index i in a zero-based array, the parent sits at ⌊(i−1)/2⌋ and the children at 2i+1 and 2i+2. Navigation is arithmetic on an index. A heap of n elements occupies exactly n slots with no per-node overhead, and its height is ⌊log₂ n⌋.

In a min-heap every node holds a key no greater than the keys of its children. The root therefore holds the minimum, and find-min reads one array slot in O(1) time. A max-heap reverses the comparison; the two are the same structure under an inverted order.

The property is a partial order, not a total one. Siblings are unrelated, subtrees at the same depth are unrelated, and an array scan does not produce sorted output. Maintaining this weaker order is what allows updates in logarithmic time; a fully sorted array would need linear work per insertion. The priority queue interface asks for nothing stronger.

Insertion appends the key at index n, the first free slot, which preserves completeness but may break the heap property on the single edge to its parent. Sift up compares the new key with its parent and swaps when the parent is larger, repeating until the parent is smaller or the key reaches the root.

Only ancestors of the inserted slot are examined, so the cost is O(log n) worst-case with at most one comparison per level. For keys inserted in random order the expected number of swaps is O(1): most keys stop within a level or two, because half the nodes are leaves. The swap chain can be replaced by shifting parents down and writing the key once at its final position, halving the memory traffic.

extract-min removes the root and must refill the hole without breaking completeness. Move the last array element into the root, shrink the length by one, then sift down: compare the displaced key with both children and swap it with the smaller child. Swapping with the larger child would place a key above its sibling and violate the property immediately.

The walk ends when the key is no larger than both children or reaches a leaf, so the cost is O(log n) worst-case. Sift down costs two comparisons per level — one to pick the smaller child, one to test the key against it — while sift up costs one. Deleting an arbitrary element at index i uses the same move-the-last-element trick, then sifts down or up depending on which direction the property breaks.

Building a heap by n successive insertions costs O(n log n). Building it in place costs O(n): run sift down on every internal node, from index ⌊n/2⌋ − 1 back to the root. The second half of the array is leaves, and a leaf is already a valid one-element heap.

The bound follows from where the nodes are. A heap holds at most ⌈n/2^{h+1}⌉ nodes of height h, and a sift down from height h costs O(h). The total is bounded by n · Σ h/2^{h+1}, and that sum converges to 1, giving O(n). Most nodes sit near the bottom and travel almost nowhere; the few expensive nodes are rare enough to pay for. The method comes from Floyd's 1964 treesort3.

Asymptotics hide the constant that dominates heap workloads. A standard extract-min performs about 2 log₂ n comparisons, because each level needs one comparison between the children and one against the sifted key. The key almost always travels back to the bottom, since it came from the bottom.

Bottom-up heapsort, described by Wegener in 1993, exploits that. It first walks the path of smaller children all the way to a leaf using one comparison per level, then walks back up to find the insertion point. The result is roughly log₂ n + O(1) comparisons per extraction on typical input, at the cost of an extra upward scan. When comparisons are expensive — long strings, tuple comparators, database keys — that halving is the difference the profile shows.

Nothing requires two children. A d-ary heap gives each node d children at indices di+1 through di+d, with the parent at ⌊(i−1)/d⌋. Height falls to log_d n, so sift up — and therefore insertion and decrease-key — gets cheaper by a factor of log d.

Sift down gets more expensive: each level now needs d−1 comparisons to find the smallest child, giving O(d log_d n) for extraction. The trade favours update-heavy workloads such as Dijkstra's algorithm, where decrease-key operations outnumber extractions. The d children are contiguous in memory, so one level of a four-ary heap frequently occupies a single cache line, which is why d = 4 is the common choice.

Heapsort builds a max-heap over the input array in O(n) time, then repeatedly swaps the root with the last unsorted slot, shrinks the heap by one, and sifts down. After n extractions the array is sorted ascending in place, with O(1) auxiliary memory and an O(n log n) worst case regardless of input order.

It is nevertheless slower than quicksort on most real inputs. Sift down jumps between array positions that grow geometrically far apart, so the access pattern defeats prefetching and the branch that selects the smaller child is hard to predict. Heapsort is also not stable. Its role in production libraries is as insurance rather than the primary sort.

Dijkstra's algorithm and Prim's algorithm need to lower the key of an element already in the queue. A plain binary heap cannot find that element: the array order carries no information about which slot holds which item, so locating it costs O(n).

An indexed heap stores a map from item identity to array position and updates it on every swap. Decrease-key then resolves the slot in O(1) and sifts up in O(log n). The alternative, used in most shortest-path code, is lazy deletion: push a second entry with the improved key and discard entries whose key no longer matches the item's best known distance when they surface. That keeps the heap simple at the cost of holding up to O(m) entries for m edges. Merging two binary heaps has no such workaround — it costs O(n), which is what the binomial heap and its descendants exist to fix.

The array layout is the binary heap's practical advantage over every pointer-based competitor. There are no child pointers, no parent pointers, and no per-node allocation: n keys occupy an array of n keys. A pointer-based heap on a 64-bit machine typically adds 24 to 32 bytes of links and marks per node, plus allocator headers.

Locality is uneven. The top of the heap stays resident in cache and is touched by every operation, while the lower levels stride across memory in steps that double each level. Once the heap exceeds cache, a sift down costs roughly one cache miss per level below the resident prefix. Increasing the arity or blocking the layout into cache-line-sized subtrees reduces that miss count without changing the asymptotics.

A binary heap gives O(1) find-min, O(log n) insert and extract-min, O(n) construction, and zero space overhead beyond the array, with implementations short enough to audit in one screen. For a bounded working set with no merge requirement, nothing else in the heap family is faster in wall-clock terms.

What it does not give: O(1) merge, O(1) decrease-key, cheap search for an arbitrary key, ordered iteration, or stable ordering among equal keys. It also invalidates positions on every operation, so external references need the index map. Workloads that meld queues constantly want a pairing heap; workloads that need ordered iteration want a search tree such as an AVL tree, not a heap at all.

Go's runtime keeps pending timers in a four-ary min-heap in runtime/time.go, ordered by firing time, with siftupTimer and siftdownTimer maintaining it as timers are added and cancelled; the scheduler reads the root to learn when it must next wake. CPython's asyncio event loop does the same job with a binary heap: BaseEventLoop holds scheduled callbacks in a heapq list called _scheduled, pushing TimerHandle objects keyed by deadline and popping expired ones into the ready queue on each iteration.

Storage engines use heaps to merge sorted runs. RocksDB's MergingIterator keeps one child iterator per memtable and SST file in a binary heap ordered by current key, so iteration and compaction see a single sorted stream over many LSM tree levels. PostgreSQL's tuplesort.c merges external sort runs with a heap holding the head tuple of each tape. The GNU C++ library's std::sort uses introsort: quicksort until the recursion depth passes 2 log₂ n, then heapsort on the remaining partition, which is what converts quicksort's quadratic worst case into a guaranteed O(n log n) bound.

A binary heap stores a complete binary tree in an array and maintains the single invariant that no child precedes its parent. Insertion sifts up, extraction moves the last element to the root and sifts down, and bottom-up construction over the internal nodes builds a heap from an unordered array in O(n) time.

Find-min is O(1), insertion and extraction are O(log n) worst-case, and space is exactly the array. The costs are an O(n) merge, a decrease-key that needs a side index, poor locality in the lower levels, and no ordered traversal. Heaps that improve on the merge and decrease-key bounds pay for it with pointers and per-node fields.