Heap Sort
Build a max-heap, then repeatedly pull the root to the back — guaranteed O(n log n) with O(1) memory.
Hands on Interactive visualization
Implementation Code
export function heapSort(a: number[]): number[] {
const n = a.length;
// Build a max-heap bottom-up: O(n). Last parent is n/2 - 1.
for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n);
// Repeatedly move the max to the back and shrink the heap.
for (let end = n - 1; end > 0; end--) {
[a[0], a[end]] = [a[end], a[0]];
siftDown(a, 0, end);
}
return a;
}
function siftDown(a: number[], root: number, end: number): void {
for (;;) {
let child = 2 * root + 1;
if (child >= end) return; // no children within the heap
if (child + 1 < end && a[child + 1] > a[child]) child++; // larger child
if (a[root] >= a[child]) return; // heap property holds
[a[root], a[child]] = [a[child], a[root]];
root = child;
}
}Big-O Complexity
Bottom-up heap construction is O(n); the n extract-max operations dominate at O(n log n).
In production When to use
The only mainstream sort with guaranteed O(n log n) time and O(1) auxiliary space — no merge buffer, no recursion stack. Ideal when memory headroom is fixed and small.
Introsort — C++'s std::sort and the pre-pdqsort Go sort — falls back to heap sort when quicksort's recursion gets suspiciously deep, converting the O(n²) worst case into O(n log n).
No pathological inputs and no allocation means worst-case execution time can be certified — a requirement in hard real-time and safety-critical firmware.
The underlying binary heap powers priority queues everywhere: schedulers, Dijkstra, top-k over streams with a bounded heap of size k in O(n log k).
When inputs are attacker-controlled, heap sort cannot be driven quadratic — an algorithmic-complexity DoS defense that plain quicksort needs randomization to match.
Trade-offs Strengths & weaknesses
- Guaranteed O(n log n) worst case — no adversarial input exists.
- In-place with O(1) auxiliary memory; iterative sift-down needs no stack.
- Immune to complexity attacks, unlike unrandomized quicksort.
- Heap construction is O(n), and partial sorting (top-k) falls out naturally.
- Predictable: best, average, and worst cases are all the same order.
- 2–3x slower than quicksort in practice: parent/child jumps have poor cache locality.
- Not stable — sift operations move equal keys past each other.
- Not adaptive: sorted input costs exactly as much as random input.
- Almost every comparison feeds a data-dependent branch, hurting modern pipelines.
- Hard to parallelize: each extract-max depends on the previous one.
Intuition Mental model
A tournament bracket with demotions
A max-heap is a tournament where every parent has beaten its children. Sorting is: crown the champion, retire them to the podium, and let the displaced challenger fight its way back down.
- Seed the bracket bottom-up: every small final settles before the rounds above — that is heapify, and it is cheap because most matches are near the bottom.
- The root now holds the champion: the maximum.
- Retire the champion to the last open podium slot at the array's end; it never plays again.
- The player yanked from the bottom to the root is probably weak: let it lose its way down to its correct level (sift-down, log n matches).
- Repeat with a bracket that shrinks by one each round — podium fills back-to-front, in ascending order.
Prep Interview questions
Why is building a heap bottom-up O(n) rather than O(n log n)?
Heap sort has better worst-case bounds than quicksort — why is quicksort still the default?
How do you find the k largest elements in a stream of n items with O(k) memory?
Why does heap sort use a max-heap for ascending order rather than a min-heap?
What is the parent/children index arithmetic for a 0-based array heap?
Watch out Common bugs
Bottom-up construction must start at the last parent, n/2 - 1, and walk down to 0. Starting at n/2, or iterating upward, leaves subtrees unheapified.
Using children 2i and 2i+1 (correct for 1-based heaps) on a 0-based array silently builds a broken heap. For 0-based: children are 2i+1 and 2i+2, parent is (i-1)/2.
The parent must swap with the larger of its two children. Comparing only the left child (or picking a child before checking it exists) violates the heap property one level down.
After swapping the root with index end, the sift-down must treat the heap as size end — including the just-placed maximum pulls sorted elements back into the heap.
One screen Cheat sheet
Heapify in O(n), then n times: swap root to the back, shrink the heap, sift the new root down.
- The only common sort that is both O(n log n) worst case and O(1) space.
- Bottom-up heapify is O(n); start at the last parent n/2 - 1.
- 0-based indexing: children 2i+1 / 2i+2, parent (i-1)/2.
- Not stable, not adaptive, cache-unfriendly — hence slower than quicksort in practice.
- Introsort's safety net: quicksort speed with heap sort's worst-case guarantee.
- Max-heap for ascending order; the sorted region grows from the back.