Heap sort

The problem it solves

You want quicksort’s speed without quicksort’s bad day, and you can’t afford merge sort’s memory. Heap sort is the only mainstream comparison sort that is simultaneously O(n log n) worst-case and O(1) extra space — no adversarial input can slow it, no allocation can fail. That’s why introsort (the sort inside C++’s standard library) uses it as the escape hatch: when quicksort’s recursion goes suspiciously deep, heap sort takes over and the guarantee holds.

The deeper reason to learn it: heap sort is a two-line consequence of a data structure. Understand the binary heap — the same heap behind every priority queue, every “top-K” problem, every Dijkstra — and heap sort is just build a heap, extract n times. The sort is almost free once the structure is understood, and interviews price them as a bundle.

The intuition — and where it breaks down

A single-elimination tournament, upside down. In a max-heap, every parent has beaten (is at least as large as) both of its children, all the way down — so the overall champion must be sitting at the root. No searching required: the structure is the search, pre-paid. Extract the champion, promote wisely, and the next champion surfaces in log n promotion steps rather than a fresh n-wide scan.

The heap’s quiet magic is that this “tournament bracket” needs no pointers at all. Lay the tree into the array level by level: the node at index i has children at 2i + 1 and 2i + 2. Parent-child arithmetic replaces memory structure — the visualization deliberately shows the heap as bars, not as a tree, because the array-in-disguise is the fact people fail to internalize.

Where the analogy breaks: a tournament ranks only the winner reliably (the runner-up might have met the champion in round one — this is a real flaw in real tournaments). A heap has the same property: beyond the root, order is only partial. The second-largest is one of the root’s children, but the smallest could be almost anywhere in the bottom half. A heap is not a sorted array wearing a costume, and treating it like one is the classic misconception.

Loading…

A walkthrough you can check

Sort [4, 1, 5, 2].

Build (sift down each internal node, deepest first): internal nodes are indices 1 and 0. Sift index 1: children of 1 are 2 — 2 > 1, swap → [4, 2, 5, 1]. Sift index 0: children of 4 are 2 and 5 — largest child 5, swap → [5, 2, 4, 1]. Max-heap complete: every parent ≥ its children.

Extract, three rounds:

1. Swap root 5 with last element 1 → [1, 2, 4 | 5]; the heap shrinks, 5 is locked. Sift 1 down: larger child 4, swap → [4, 2, 1 | 5].
2. Swap 4 with 1 → [1, 2 | 4, 5]; sift: swap with 2 → [2, 1 | 4, 5].
3. Swap 2 with 1 → [1 | 2, 4, 5]. One element is trivially a heap. Sorted.

The sorted region grows from the right, largest first — exactly selection sort’s pattern, run in reverse order of magnitude, with the O(n) scan replaced by an O(log n) sift. The prediction prompts push on the two facts this walkthrough demonstrates: where the maximum always is (index 0, by invariant), and where it goes (the last live slot, by design).

The invariant

Two regions, one boundary. Left of the boundary: a valid max-heap — every parent at least its children. Right: the largest elements ever extracted, in final sorted order. Each extraction moves the boundary one left, and the sift-down repairs the single invariant violation the root-swap created. The sift’s own invariant is local: at each step, only the node being sifted might violate heap order with its children; everything else is already valid — which is why one root-to-leaf path suffices.

Complexity, derived

Extraction: n − 1 rounds, each a swap plus a sift down a tree of height ⌊log₂ n⌋ — O(n log n), and no input order changes the tree’s height, hence no meaningful best case. Run the sorted and reversed presets: the comparison counters land within a few percent of each other, and that indifference is the guarantee made visible.

Build: the famous surprise. Sifting every internal node looks like O(n log n), but sift cost is bounded by node height, and heights are wildly skewed toward zero: half the nodes are leaves (height 0, free), a quarter have height 1, an eighth height 2… The sum Σ (n / 2^(h+1)) · h converges to O(n). Building the heap is linear — the interview follow-up with the highest miss rate on this entire page, and the reason “heapify then extract-k” beats “sort then take k” for top-K problems.

Space: O(1). Stability: no — the root-to-end long-distance swap reorders equals freely, and there is no practical stable heap sort. The honest performance caveat: index-doubling access patterns jump across memory, so heap sort’s cache behaviour is the worst of the three n log n sorts — which is why it’s the fallback in introsort rather than the default.

What people get wrong

Building with sift-up instead of sift-down. Inserting elements one at a time sifts up, costing O(n log n) — correct but forfeits the linear build and, in an interview, forfeits the follow-up.

Sifting from the wrong starting point. The build must start at the last internal node, n/2 − 1, and walk to 0. Starting at 0 sifts against unheapified subtrees and produces garbage that sometimes accidentally sorts small tests.

Using the original size during extraction. The heap shrinks; sifting with the full n resurrects locked elements back into the heap. The shrinking boundary is the algorithm.

“A heap is a sorted array.” Covered above; it’s the misconception behind wrong answers to “where is the minimum in a max-heap?” (anywhere in the leaves — the bottom half — not at the end).

Implementation notes across languages

Python’s heapq is a min-heap with no key parameter — for max-heap behaviour you negate values or wrap in tuples, and interviewers know the dance. heapq.heapify is the linear build; nlargest/nsmallest are the top-K shortcuts. Java’s PriorityQueue takes a comparator (Comparator.reverseOrder() for max) but its iteration order is heap order, not sorted order — printing it is a classic confusion. C++ has the honest toolkit: std::make_heap / push_heap / pop_heap operate on your own vector, and std::sort_heap is literally the extraction phase — heap sort decomposed into library calls. In JavaScript there is no standard heap; writing sift-down cleanly from scratch is therefore a fair and common interview exercise.