Heapsort
Imagine you must sort ten million records with a strict memory budget. There can be no extra arrays, no recursion stack blowing up. You also need a hard guarantee that no adversarial input can make you slow. Quicksort usually wins on average but has a Θ(n²) worst case. A clever adversary can trigger that worst case. Merge Sort guarantees Θ(n log n) but needs Θ(n) extra space to merge. Heapsort threads the needle: it sorts in place, using only O(1) extra memory. It guarantees Θ(n log n) time on every input, best case to worst case. There is no randomness and no adversarial weakness. The trick is to combine two ideas you already know. Selection Sort repeatedly finds the maximum remaining element and moves it to the end. This is correct, but O(n) per search makes it Θ(n²) overall. Binary Heaps answer "what is the maximum?" in O(1). They also let you remove it and restore order in O(log n). Heapsort is exactly selection sort with the linear scan replaced by a heap. First, build a max-heap once in Θ(n) time. Then perform n extract-max operations, each Θ(log n). Each one places the next-largest untouched element into its final sorted position at the end of the array. The elegance of heapsort is that the heap lives inside the very array being sorted. The unsorted prefix is a valid max-heap. The sorted suffix grows one element at a time from the back. There is no auxiliary array, no linked structure, no pointers. It is just index arithmetic on one array. This is why heapsort is prized in memory-constrained systems and embedded firmware. It also serves as a fallback inside hybrid sorts like `introsort` (used in many C++ standard library implementations). This caps worst-case behavior when quicksort's recursion goes too deep. This article develops heapsort from the array-as-tree representation. It walks through `BUILD-MAX-HEAP` and `HEAPSORT` line by line. It proves the Θ(n log n) bound, including the subtler Θ(n) proof for heap construction. It traces a full example and flags the classic pitfalls. Especially notable is heapsort's most consequential limitation: it is not stable. This property foreshadows deeper questions about what any comparison-based sort can and cannot guarantee. That is the theme of the Comparison-Sort Lower Bound.
- Heapsort = Selection Sort with the "find the max" step upgraded from O(n) to O(log n) using a binary heap.
- Two phases: `BUILD-MAX-HEAP` turns the array into a max-heap in Θ(n) time; then n rounds of extract-max sort it in place.
- Worst-case, average-case, and best-case running time are all Θ(n log n) — no adversarial input can slow it down.
- Space complexity is O(1) extra (in-place) — no auxiliary array, unlike merge sort.
- Heapsort is not stable: equal keys can be reordered, because heap operations swap distant elements.
- It underlies hybrid sorts (e.g. introsort) as a guaranteed-safe fallback and appears in priority-queue-based scheduling.
Heapsort replaces selection sort's linear "find the maximum" scan with a logarithmic heap operation, turning an O(n²) idea into a Θ(n log n) in-place, worst-case-optimal comparison sort.
The idea
A binary heap stored in an array `A[1..n]` (1-indexed for clean arithmetic) represents a complete binary tree where node `i` has children at indices `2i` and `2i+1`, and parent at `⌊i/2⌋`. The max-heap property requires `A[⌊i/2⌋] ≥ A[i]` for every node `i` other than the root — every parent is at least as large as its children. This implies the maximum element of the whole heap always sits at `A[1]`, retrievable in O(1) time, and it implies nothing about the relative order of siblings or of equal-valued nodes anywhere in the tree. Heapsort exploits this in two phases. First, `BUILD-MAX-HEAP` converts an arbitrary array into one satisfying the max-heap property, working bottom-up over all non-leaf nodes. Second, the sorting loop repeatedly (a) swaps the root (the current maximum) with the last element of the still-unsorted prefix, (b) shrinks the heap's logical size by one so that swapped element is now permanently excluded from the heap, and (c) calls `MAX-HEAPIFY` at the root to restore the heap property in the shrunken heap. After `n − 1` such rounds the array is sorted in place, ascending, with the heap's logical size having shrunk from `n` down to `1`. The key subroutine, `MAX-HEAPIFY(A, i)`, assumes the subtrees rooted at `2i` and `2i+1` are already valid max-heaps, but `A[i]` itself may violate the property. It finds the largest of `A[i]`, `A[2i]`, `A[2i+1]`, swaps it into position `i` if it isn't already `A[i]`, and recurses into whichever child received the old `A[i]`. This "sift-down" runs in O(log n) because it follows a single root-to-leaf path in a tree of height ⌊log₂ n⌋.
How it works
The algorithm has three layers: `MAX-HEAPIFY` (the repair primitive), `BUILD-MAX-HEAP` (applies it bottom-up to establish the invariant), and `HEAPSORT` (the outer loop that extracts maxima). ``` MAX-HEAPIFY(A, i, heap_size) l ← 2i r ← 2i + 1 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 swap A[i] and A[largest] MAX-HEAPIFY(A, largest, heap_size) // sift down along one path BUILD-MAX-HEAP(A, n) heap_size ← n for i ← ⌊n/2⌋ downto 1 MAX-HEAPIFY(A, i, heap_size) // Leaves (indices ⌊n/2⌋+1 .. n) are trivially valid heaps of size 1; // processing i from the last internal node up to the root // guarantees the "subtrees below i are already heaps" precondition holds. HEAPSORT(A, n) BUILD-MAX-HEAP(A, n) heap_size ← n for j ← n downto 2 swap A[1] and A[j] // move current max to its final slot heap_size ← heap_size - 1 // shrink the heap, excluding A[j] MAX-HEAPIFY(A, 1, heap_size) // restore heap property at the root // A[1..n] is now sorted in ascending order ``` Two implementation notes that matter in practice. First, `MAX-HEAPIFY` is naturally recursive but is easily rewritten iteratively (a `while` loop following the "largest" pointer down), which avoids recursion-stack overhead — a detail that matters for the in-place, low-overhead selling point of heapsort. Second, the array can be 0-indexed with children at `2i+1`, `2i+2` and parent at `⌊(i−1)/2⌋`; the algorithm is identical, only the arithmetic shifts.
Complexity & correctness
Correctness of `MAX-HEAPIFY`. By the stated precondition, the subtrees rooted at children `2i` and `2i+1` are already valid max-heaps. The procedure examines `A[i]` and its two children and finds the true largest among the three. If it's `A[i]`, no violation exists and the recursion stops. Otherwise the largest child is swapped into position `i`; now `A[i]` is correctly the maximum of that triple, but the subtree that donated its root may now be violated at exactly one node — the child position that received the old, possibly-small `A[i]`. Recursing there, with the same precondition (its own children's subtrees are untouched, still valid heaps), inductively restores the entire subtree. This is an induction on subtree height: base case (leaf, height 0) is trivially a heap; inductive step is exactly the argument above.
Correctness of `BUILD-MAX-HEAP`. Processing internal nodes in decreasing order of index, from `⌊n/2⌋` down to `1`, guarantees that whenever `MAX-HEAPIFY(A, i, n)` is called, both children subtrees rooted at `2i` and `2i+1` are already valid max-heaps — either because they are leaves (indices `> ⌊n/2⌋`, automatically valid single-node heaps) or because they were already fixed by an earlier, higher-indexed call. This is a loop invariant: at the start of each iteration of the `for` loop, the subtrees rooted at `i+1, i+2, …, n` are all valid max-heaps. It holds initially (vacuously, for `i = ⌊n/2⌋`, since indices `> ⌊n/2⌋` are leaves) and is maintained by the correctness of `MAX-HEAPIFY` just argued; when `i` reaches `0` the whole array `A[1..n]` is a max-heap, proving termination correctness.
Correctness of `HEAPSORT`. The outer loop invariant: at the start of iteration `j`, `A[1..j]` is a max-heap and `A[j+1..n]` contains the `n − j` largest elements of the array, already in final sorted position. Initially (`j = n`, after `BUILD-MAX-HEAP`) the suffix is empty and `A[1..n]` is a heap — trivially true. Each iteration swaps the current max `A[1]` into slot `j`, which is correct because `A[1]` is (by the heap property) at least as large as everything remaining in `A[1..j]`, hence it belongs at or after position `j`, and since positions `j+1..n` already hold the larger elements sorted, position `j` is exactly right. Shrinking `heap_size` and re-heapifying restores a valid heap on `A[1..j−1]` for the next round. When the loop ends (`j = 1`), `A[1]` — the sole remaining element — is trivially the smallest, and the array is fully sorted.
Time complexity of `MAX-HEAPIFY`. In the worst case the element sifts from the root to a leaf, a path of length at most `⌊log₂ n⌋` in a tree with `n` nodes, and each level does O(1) work (two comparisons, at most one swap). So `MAX-HEAPIFY` is O(log n).
Time complexity of `BUILD-MAX-HEAP` — the subtle Θ(n) bound. A naive bound of `n · O(log n) = O(n log n)` is correct but loose. The tight analysis counts work by height rather than by call: a heap of `n` nodes has at most `⌈n / 2^{h+1}⌉` nodes at height `h`, and `MAX-HEAPIFY` on a node of height `h` does O(h) work. Summing over all heights: ``` Σ (h=0 to ⌊log n⌋) ⌈n / 2^(h+1)⌉ · O(h) = O( n · Σ (h=0 to ∞) h / 2^h ) = O(n · 2) [since Σ h/2^h = 2, a standard convergent series] = O(n) ``` Most nodes are near the bottom (half the nodes are leaves, needing zero work; a quarter are at height 1, needing O(1) work), so the total collapses to linear rather than `n log n`. This is a genuinely different — and tighter — bound than the per-call worst case would suggest, and it's the reason "building" a heap is cheaper than "sorting" one.
Time complexity of the sort loop. There are `n − 1` iterations, each doing O(1) work (a swap, a decrement) plus one `MAX-HEAPIFY` call costing O(log n). Total: `(n−1) · O(log n) = O(n log n)`.
Overall. `HEAPSORT = Θ(n) [build] + Θ(n log n) [sort loop] = Θ(n log n)`, and this bound is tight in the best, average, and worst case simultaneously — there is no input-dependent fast path, unlike quicksort (which degrades to Θ(n²) on adversarial or already-sorted input under a naive pivot rule) or insertion sort (Θ(n) best case on nearly-sorted data). This uniformity is exactly why heapsort is chosen when a hard worst-case guarantee matters more than typical-case speed.
Space. All operations are swaps within `A`; only O(1) auxiliary variables (`l`, `r`, `largest`, `heap_size`, loop counters) are needed. Heapsort is in-place: O(1) extra space, versus Θ(n) for merge sort's merge buffers.
The non-stability tradeoff. Stability means equal-key elements preserve their relative input order. Heapsort routinely violates this: `MAX-HEAPIFY` can swap an element past an equal one that was originally to its left, and the initial `BUILD-MAX-HEAP` phase reshuffles equal keys with no memory of original order. This is not a fixable implementation detail — it is structural, a direct consequence of using array-position swaps driven only by comparisons, disconnected from input order. If stability is required (e.g., sorting student records by grade while preserving name order among ties), heapsort is the wrong tool; Merge Sort is stable at the cost of Θ(n) extra space.
Worked example
Sort `A = [4, 10, 3, 5, 1]` (n = 5, 1-indexed conceptually; shown 0-indexed below with array positions labeled 1..5 for heap arithmetic).
Phase 1 — `BUILD-MAX-HEAP`: internal nodes are `i = ⌊5/2⌋ = 2` down to `i = 1`.
| Step | i | A before | Action | A after |
|---|---|---|---|---|
| start | — | [4,10,3,5,1] | — | — |
| i=2 | 2 | [4,10,3,5,1] | children of A[2]=10 are A[4]=5, A[5]=1; 10 already largest | [4,10,3,5,1] |
| i=1 | 1 | [4,10,3,5,1] | children of A[1]=4 are A[2]=10, A[3]=3; largest=10 at index 2 → swap | [10,4,3,5,1] |
| recurse at i=2 | 2 | [10,4,3,5,1] | children of A[2]=4 are A[4]=5, A[5]=1; largest=5 at index 4 → swap | [10,5,3,4,1] |
| recurse at i=4 | 4 | [10,5,3,4,1] | leaf, no children | done |
Heap built: `[10, 5, 3, 4, 1]`. Check: `A[1]=10 ≥ A[2]=5, A[3]=3`; `A[2]=5 ≥ A[4]=4, A[5]=1`. Valid max-heap.
Phase 2 — extraction loop:
| j (heap_size before shrink) | Swap A[1]↔A[j] | Array after swap | heap_size after | Re-heapify at root | Array after heapify |
|---|---|---|---|---|---|
| 5 | swap A[1]=10, A[5]=1 | [1,5,3,4,10] | 4 | sift 1 down: children 5,3 → swap w/5 (idx2); children of idx2 now idx4=4 → swap → [4] leaf | [5,4,3,1,10] |
| 4 | swap A[1]=5, A[4]=1 | [1,4,3,5,10] | 3 | sift 1 down: children 4,3 → swap w/4 (idx2); idx2's children out of range (heap_size=3, only idx4,5 don't count) | [4,1,3,5,10] |
| 3 | swap A[1]=4, A[3]=3 | [3,1,4,5,10] | 2 | sift 3 down: only child A[2]=1, 3≥1, stop | [3,1,4,5,10] |
| 2 | swap A[1]=3, A[2]=1 | [1,3,4,5,10] | 1 | heap_size=1, no children, stop | [1,3,4,5,10] |
Final array: `[1, 3, 4, 5, 10]` — correctly sorted ascending. Note how `10`, `5`, `4`, `3`, `1` were peeled off the root one at a time and packed onto the growing sorted suffix from the right, exactly mirroring selection sort's "repeatedly extract the max" strategy, but with each extraction costing O(log n) instead of O(n).
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Off-by-one in child indices | Mixing 0-indexed (`2i+1`, `2i+2`) and 1-indexed (`2i`, `2i+1`) formulas | Pick one convention and use it consistently throughout `MAX-HEAPIFY` and `BUILD-MAX-HEAP` |
| Forgetting to shrink `heap_size` before re-heapifying | Re-heapifying with the old size lets `MAX-HEAPIFY` "see" the already-sorted suffix and corrupt it | Decrement `heap_size` immediately after the swap, before calling `MAX-HEAPIFY` |
| Starting `BUILD-MAX-HEAP` loop at `i = 1` instead of `⌊n/2⌋` | Wastes calls on leaves (no-ops) but more importantly some implementations then skip the correctness precondition if done top-down instead of bottom-up | Loop must run from the last internal node down to the root, never the reverse |
| Assuming heapsort is stable | Confusing "deterministic" with "stable"; heapsort is deterministic but swaps break relative order of equal keys | If stability matters, use merge sort or a stable variant with tie-breaking indices |
| Using recursive `MAX-HEAPIFY` in a memory-critical or deeply-nested setting | Recursion adds stack frames proportional to O(log n) — usually fine, but avoidable | Rewrite as an iterative `while` loop following the "largest" pointer down |
| Treating build-heap as Θ(n log n) | Applying the naive "n calls times O(log n) each" bound without the height-weighted sum | Remember the tighter Θ(n) proof: most nodes are near the leaves and cost O(1) |
Pioneers & history
Heapsort was invented by J. W. J. Williams in 1964 as the algorithm that introduced the binary heap data structure itself — the heap was invented specifically to make this sort possible. Robert W. Floyd improved the construction phase shortly after, giving the linear-time `BUILD-MAX-HEAP` (via bottom-up heapify) used today instead of Williams's original repeated-insertion approach, which built the heap in Θ(n log n).
Origins · 1 minJ. W. J. Williams and how this was discovered
Where this matters
Heapsort's O(1) extra space and guaranteed Θ(n log n) worst case make it the standard fallback inside introsort, the hybrid algorithm behind `std::sort` in several major C++ standard library implementations: quicksort runs by default for its excellent average-case speed, but if recursion depth exceeds a threshold (a signal of adversarial or pathological input), the algorithm switches to heapsort to guarantee the worst case never degrades to Θ(n²). This hybrid design gives programmers "quicksort speed with heapsort safety" without the programmer choosing either explicitly. Beyond general-purpose sorting, the extract-max mechanism at heapsort's core — the binary heap with its O(log n) insert and extract-max — is the same structure behind priority queues used in Dijkstra's shortest-path algorithm, Prim's minimum spanning tree algorithm, event-driven simulation schedulers, and operating-system task schedulers that always need "the next most urgent item" in sublinear time. Memory-constrained embedded systems and real-time systems favor heapsort specifically because its in-place, allocation-free nature avoids garbage-collection pauses or heap-fragmentation risk (the memory-management kind of heap, not to be confused with the data structure), and its worst-case bound gives hard real-time guarantees that quicksort cannot. Heapsort's contrast with Selection Sort (same "repeatedly extract max" strategy, but O(n) per extraction instead of O(log n)) is a canonical teaching example of how a smarter data structure transforms an algorithm's asymptotic class entirely. Its contrast with Merge Sort on stability and space usage is a canonical example of algorithmic tradeoffs with no free lunch. And its Θ(n log n) worst-case optimality previews the deeper question addressed by the Comparison-Sort Lower Bound: no comparison-based sort can beat Θ(n log n) in the worst case, meaning heapsort — despite being far from the fastest sort in practice — is asymptotically as good as any comparison sort can ever be.
Ask the tutor: How does the height-weighted sum in the BUILD-MAX-HEAP proof actually evaluate to a constant, step by step?
Is heapsort faster than quicksort in practice?
Usually not. Quicksort typically has better constant factors and cache behavior because it accesses memory more sequentially, while heapsort's parent-child index jumps (`i`, `2i`, `2i+1`) scatter memory accesses across the array, hurting cache locality. Heapsort's advantage is not average-case speed but worst-case guarantee: quicksort with a naive pivot can degrade to Θ(n²) on adversarial or already-sorted input, while heapsort never exceeds Θ(n log n) regardless of input. This is why production sorts (like introsort) use quicksort by default and fall back to heapsort only when recursion depth signals trouble.
Can heapsort be made stable?
Not without extra space or overhead that erodes its main advantage. One workaround is to augment each key with its original index and break ties by index during comparisons, effectively making equal keys distinguishable and forcing a stable-equivalent order — but this requires extra storage per element and extra comparison logic, partially defeating the in-place, low-overhead appeal of heapsort. In practice, if stability is a hard requirement, it's simpler to use a naturally stable algorithm like merge sort or a stable variant of insertion/binary insertion sort for small inputs.
Why is BUILD-MAX-HEAP Θ(n) while sorting still costs Θ(n log n)?
Build-heap does bottom-up repairs where most nodes are near the leaves and need almost no work — half the nodes are leaves needing zero sifting, a quarter need at most one swap, and so on, and this geometric weighting sums to Θ(n). The sorting loop, by contrast, calls `MAX-HEAPIFY` on the root of a shrinking heap every single time, and the root is always at maximum height, so every one of the n extractions costs the full O(log n) in the worst case. Different call patterns against the same subroutine yield very different aggregate costs — that's the core insight of the amortized analysis.
What happens if the input array has duplicate keys?
Heapsort handles duplicates correctly in the sense that the final array is still sorted (non-decreasing), since `MAX-HEAPIFY` uses ≥ comparisons consistently and duplicates simply satisfy the heap property trivially among themselves. What it does not preserve is the relative order of those duplicates from the input — this is precisely the non-stability property. Correctness of value ordering is unaffected; only the tie-breaking order among equal elements is unpredictable.
How does heapsort compare to using a library priority queue to sort?
They're essentially the same algorithm at heart: inserting all n elements into a priority queue and then extracting the minimum (or maximum) n times costs Θ(n log n) using a binary heap, matching heapsort's bound. The difference is that heapsort builds the heap in place in Θ(n) via bottom-up heapify, avoiding n separate Θ(log n) insertions (which would cost Θ(n log n) just to build), and it reuses the same array rather than allocating a separate heap structure. So heapsort is a specialized, memory-lean instance of "sort via priority queue."
Why does the analysis of MAX-HEAPIFY use tree height rather than the number of nodes?
Because the cost of one call is proportional to how far an element sifts down, which is bounded by the height of the subtree it starts in, not by how many nodes exist overall. A node near the bottom of the tree (large index, small height) can only sift a short distance even though there are many such nodes; a node near the root (small index, large height) could sift the whole way down, but there is only one such node. Weighting by height and summing over the geometric distribution of node-counts-per-height is what produces the tight Θ(n) bound for the whole build phase.
Does heapsort ever get used when data is already almost sorted?
It gains almost nothing from near-sorted input, unlike insertion sort (which drops to Θ(n) on nearly sorted data) or an optimized merge sort with a pre-check. `BUILD-MAX-HEAP` and every `MAX-HEAPIFY` call in the extraction loop still do their full worst-case work regardless of input order, because the algorithm's structure depends only on array positions and heap shape, not on how close values already are to sorted order. This is part of the same coin as its strength: uniform Θ(n log n) behavior means no best-case speedup, but also no worst-case collapse.