Heap Operations — Priority Queue Implementation

Why it matters

Priority queues are one of the most-used data structures. Wrong choice (linked list vs sorted array vs heap) has 100x impact on performance. Heaps are usually the answer.

The architecture

Array representation: parent(i) = (i-1)/2, left(i) = 2i+1, right(i) = 2i+2. No pointers needed.

Insert: append at end, bubble up (swap with parent while out of order). O(log n).

Extract-min: return root, move last to root, bubble down (swap with smaller child). O(log n).

How it works end to end

Heapify: convert unordered array to heap in O(n). Bubble down from last non-leaf backwards. This is faster than n inserts.

Heap sort: heapify array, then repeatedly extract-min into a result. O(n log n), in-place, not stable.

d-ary heaps: nodes have d children instead of 2. Shallower tree, more comparisons per level. Sometimes faster in practice.

Fibonacci heap: better amortized decrease-key. Theoretically improves Dijkstra to O(E + V log V).

The array layout: a tree with no pointers

A binary heap is a complete binary tree - every level is full except possibly the last, which fills left to right. That single shape invariant is what makes the pointer-free representation work. Because there are never holes, the nodes can be written into a flat array in breadth-first order, and the tree edges become arithmetic on the index rather than memory the structure has to store.

With zero-based indexing, the children of node i live at 2i+1 and 2i+2, and the parent of a non-root node i is (i-1)/2 under integer division. One-based indexing is slightly cheaper and is what most textbook pseudocode uses: children are 2i and 2i+1, the parent is i/2, so both directions are a single shift. The saving is one add per level, which matters only in the innermost loop of a hot sift, but it is the reason production heaps often waste slot zero.

The payoff over a pointer-based tree is not asymptotic, it is constant-factor and it is large. A heap of n 8-byte keys occupies exactly 8n bytes. A node-per-element binary search tree of the same data carries two or three pointers plus an allocator header per node, so it costs three to five times the memory and scatters those nodes across the address space. The heap's top levels - the ones every operation touches - are a few hundred bytes that stay resident in L1 indefinitely. There is also no allocation on insert and no deallocation on extract, which removes an entire class of latency spikes from the operation.

Sift-up and sift-down are not symmetric

Both directions are described as O(log n), and both are, but they behave very differently and the asymmetry drives most heap tuning.

Sift-up does one comparison per level. A node has exactly one parent, so restoring the invariant upward means comparing against that parent and stopping the moment the order holds. The worst case is the full height, but the average case for a randomly ordered insert is close to constant: roughly half the nodes are leaves, a quarter sit one level up, and so on, so a key landing in a random position stops after a small constant number of comparisons. Pushing a batch of unordered keys therefore costs far less than the log-n-per-insert bound suggests.

Sift-down does two comparisons per level - one to pick the smaller child, one to test that child against the moving key - and it rarely stops early. The element being sifted down after an extract is the last element of the array, which is a leaf, which means it is statistically one of the larger keys in the structure. It usually travels most of the way back to the bottom. Extract-min really does pay close to 2 log n comparisons, while insert usually pays a handful. If you are profiling a heap-heavy loop, the extracts are where the time is.

Floyd's optimisation exploits exactly this. Instead of testing at every level whether the moving key has come to rest, sift it down unconditionally along the path of smaller children all the way to a leaf, then sift it back up. The downward pass drops to one comparison per level, and the upward correction is short because the key was large to begin with. It roughly halves the comparison count of extract-min, which is worthwhile when comparisons are expensive - string keys, tuples, or a user-supplied comparator - and not worth the complexity when keys are machine integers.

Why building a heap is O(n), not O(n log n)

Converting an unordered array into a heap by sifting down from the last internal node backwards costs linear time, and the reason is worth working through because the naive count gives the wrong answer.

The naive count says: n/2 internal nodes, each sifting down up to log n levels, therefore O(n log n). That is a valid upper bound and it is loose, because it charges every node the height of the whole tree. The real cost depends on each node's own height above the leaves, and the node population is wildly skewed toward the bottom.

At height h above the leaves there are at most n / 2^(h+1) nodes, and sifting one of them down costs O(h). Summing over the tree gives n/2 multiplied by the series h / 2^h for h from 0 upward. That series converges to 2, so the total work is bounded by n - a constant, not a logarithm.

The intuition behind the algebra: half the nodes are leaves and do zero work, a quarter can move at most one level, and only the single root can fall the full log n. The expensive nodes are exactly the rare ones. Inserting the same keys one at a time inverts this - there, the many leaf-level insertions are the ones that can travel the full height - which is why repeated insertion really is O(n log n) and bottom-up construction is not.

def sift_down(a, i, n):
    while True:
        c = 2 * i + 1                 # left child
        if c >= n:
            return
        if c + 1 < n and a[c + 1] < a[c]:
            c += 1                    # pick the smaller child
        if a[i] <= a[c]:
            return                    # invariant restored
        a[i], a[c] = a[c], a[i]
        i = c

def build_heap(a):
    # last internal node is at (len(a) // 2) - 1; leaves need no work
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i, len(a))

One thing linear construction does not buy you is a sorted array. The heap property is far weaker than a total order - it constrains each node only against its own descendants - so there is no conflict with the comparison-sorting lower bound. That bound and the general complexity vocabulary are developed in Big-O Notation.

Heapsort: in-place, worst-case optimal, and usually second place

Heapsort falls out of the two primitives. Build a max-heap over the array in linear time, then repeatedly swap the root with the last live slot, shrink the live region by one, and sift the new root down. After n-1 rounds the array is sorted ascending, and the sorted suffix has been accumulating in exactly the space the heap vacated.

Its properties are unusually clean. It is genuinely in-place - a constant number of scratch variables, no recursion, no auxiliary array. Its worst case is O(n log n), with no adversarial input that degrades it, unlike quicksort's quadratic worst case. It is not stable: equal keys are flung across the array by sifts and their relative order is destroyed.

And yet on typical hardware it loses to a decent quicksort by a factor of two or more. The reason is memory access, not instruction count. Sifting down walks i -> 2i+1 -> 4i+3, so the stride doubles at every level; once the live region exceeds the last-level cache, each step of the descent is a fresh cache miss with no useful prefetch, and the deeper the heap the worse the ratio. Quicksort's partition is two sequential scans converging on each other, which is the access pattern hardware prefetchers were designed for. Heapsort also does more comparisons per element than a well-tuned quicksort, and every one of its swaps is long-distance.

So heapsort's production role is as an insurance policy rather than a primary algorithm. Introsort - the strategy behind the C++ standard library's std::sort - runs quicksort, tracks recursion depth, and switches the current subrange to heapsort once the depth exceeds roughly 2 * log2(n). Quicksort handles the common case at full speed; heapsort caps the worst case, guaranteeing O(n log n) against inputs crafted to defeat the pivot choice. The same library's partial_sort is heap-based for the same structural reason: a bounded heap is the natural way to keep the best k seen so far without sorting the rest. That bounded-k pattern belongs to Partial Sort and Top-K / heavy hitters rather than here.

d-ary heaps and the cache-line argument

Nothing about the array encoding requires two children. In a d-ary heap the children of i occupy the contiguous run d*i+1 through d*i+d, and the parent is (i-1)/d. The tree becomes shallower - depth log_d n instead of log_2 n - and the two sift directions move in opposite directions as a result.

Sift-up gets strictly cheaper. It costs one comparison per level, so raising d divides its work by log d; a 4-ary heap halves the sift-up path against a binary heap, an 8-ary heap cuts it to a third. Sift-down gets more expensive, because finding the smallest of d children costs d-1 comparisons per level. Multiply that by the depth and the total comparison count for a descent grows as (d-1) / ln d, which increases with d without bound. Purely on comparison count, binary wins for extraction.

Comparison count is not the whole cost on real hardware, which is why 4-ary and 8-ary heaps routinely beat binary ones in benchmarks. The d children are adjacent in memory. Scanning them is a linear walk over one or two cache lines, and a 64-byte line holds eight 8-byte keys - so with d=8 and the array padded so sibling groups align to line boundaries, an entire sibling group is one cache miss. A binary heap pays a miss per level too, but it has three times as many levels to descend. Trading a handful of extra comparisons, which run out of registers, for a third of the cache misses is a good trade whenever the heap is larger than the last-level cache. Past about d=8 the trade reverses: comparison work keeps growing linearly while depth only shrinks logarithmically, and the sibling group stops fitting in a line or two.

The other reason to reach for a d-ary heap is workloads that are insert-heavy or decrease-key-heavy relative to extraction, since those are the operations that ride the cheap upward path.

Decrease-key needs a handle, and that is the real cost

The array encoding gives fast access to the root and to any index, and no way whatsoever to locate a particular element. Finding one is a linear scan. So decrease-key and arbitrary delete, which every graph algorithm wants, are not natively supported operations - they are operations you have to build scaffolding for.

The scaffolding is a map from element identity to current array index, and the expensive part is keeping it honest: every swap performed by every sift must update two entries in that map. This roughly doubles the write traffic of each sift and inserts a hash lookup or an indirection into the innermost loop. Java's PriorityQueue is the standard illustration of the alternative choice - it maintains no such map, so remove(Object) is documented as linear time, because it has to scan for the element before it can fix up the array.

Two escape hatches cover almost every real case:

An index array, when identities are dense integers. If your elements are graph vertices numbered 0..V-1, the map is a plain int[V] holding each vertex's current heap position. Updates are two stores into a small hot array, with no hashing and no allocation. This is cheap enough to be the right answer whenever it applies.

Lazy deletion, when they are not. Skip the map entirely. To lower a key, push a second entry with the better value and leave the stale one in place; on pop, discard any entry whose recorded key no longer matches the current best for that element - the familiar if key > best[u]: continue guard. The heap can grow to one entry per relaxation rather than one per element, so it is asymptotically worse in space and in the log factor, and it still usually wins, because every operation stays a bare push or pop with no bookkeeping and pushes are the cheap direction.

This is also the practical reason the exotic heaps with better decrease-key bounds so rarely pay off. Their improvements are amortised and carry heavy constants and pointer chasing, while the binary heap's decrease-key problem usually dissolves into lazy deletion. Those structures have their own articles: Fibonacci Heap, Pairing Heap and Leftist Heap. The shortest-path side of the story lives in Dijkstra and Dijkstra with a Fibonacci Heap.

Failure modes that bite in production

Heaps are not stable, and the instability is not deterministic. Equal keys emerge in an order determined by the array permutation at that instant, so the same multiset inserted in the same order can come out differently depending on what else was in the heap. If ties must break FIFO, make the key a pair of priority and a monotonically increasing sequence number. The classic bug here is the half-fix: a tuple of (priority, payload) compares fine until two priorities are equal, at which point the comparator falls through to the payload, and if the payload is not comparable the whole thing raises at some arbitrary later moment under load rather than at insert time.

Mutating a key while its element is in the heap silently corrupts the structure. There is no validation and no crash - the invariant simply stops holding on the path from that node, and pops start returning wrong answers that look like application bugs. Store an immutable snapshot of the ordering key in the heap entry and keep the mutable object behind it.

Do not read a heap as a sorted sequence. Only the root is guaranteed. Slots 1 and 2 are the two candidates for second place, but slot 3 can hold anything at all, and iterating the backing array yields an order with no useful meaning. Any code that iterates a heap to display "the top ten" is wrong past the first element.

Merging two binary heaps is O(n+m). There is no cheap meld - the usual approach is to concatenate the arrays and rebuild bottom-up, which at least gets linear rather than m log n from re-inserting. This is the one operation binary heaps are genuinely bad at, and it is the entire reason mergeable heaps exist. If your workload melds often, a binary heap is the wrong structure.

On the credit side, growth is unusually cheap. Doubling a dynamic array backing a heap is a flat memcpy with no pointer fixups to perform, because there are no pointers - so amortised growth costs a bulk copy and nothing else. Presize when you know the bound and even that disappears. And peek is a single array read, which is why heaps are the right structure for the "what expires soonest" loop that timers and timeout wheels are built around.

When a binary heap is the wrong answer

A binary heap is a specialist: it is close to optimal for extract-min over unbounded keys, in memory, on one thread, and mediocre or worse at everything adjacent. Some alternatives worth weighing:

A sorted array gives O(1) peek and O(n) insert, and beats a heap outright when the collection is tiny or reads dominate writes. For fewer than roughly a dozen elements a linear insertion into a contiguous array is faster in wall-clock terms than any log-n structure, because the whole thing lives in one or two cache lines.

A balanced BST or skip list costs O(log n) for the same operations but also gives ordered iteration, predecessor and successor queries, and arbitrary deletion without a side map. You pay two to three times the constant factor and the pointer overhead. Take it when you need more than the minimum - see Skip list architecture.

A bucket queue or timer wheel is O(1) per operation when priorities are small bounded integers or timestamps within a known horizon, because it replaces comparison with array indexing. Schedulers and timeout managers almost always want this rather than a heap.

Concurrency changes the answer entirely. Every heap operation touches the root and mutates the array shape, so the structure is a single hot contention point and is notoriously hard to make lock-free - see Lock-Free Queues. The pragmatic designs shard into per-thread heaps and steal, or accept a mutex around a heap small enough that the critical section is short. Once priority handling becomes a service-level concern - fairness, aging, starvation, admission - the data structure stops being the interesting part; that ground belongs to Priority queue service architecture.