Heaps and Heapsort

Quicksort is fast but has a quadratic worst case; mergesort guarantees $\Theta (n\log n)$ but needs $\Theta (n)$ scratch space. $\text{Heapsort}$ captures the best of both: a worst-case $\Theta (n\log n)$ bound and sorting in place, using only a constant amount of extra memory. The trick is a data structure, the binary heap, which doubles as an efficient priority queue and so is worth knowing for its own sake well beyond sorting.

The heap as a tree we never build

A (binary) max-heap is a complete binary tree that obeys one local rule.¹

Complete means the tree is filled level by level, top to bottom and left to right, with no gaps until possibly the last level. That rigidity is what lets us discard the tree entirely and store it as a flat array: there is exactly one shape for a complete tree on $n$ nodes, so position in the array is position in the tree.

We store the heap in an array $A[\mathrm{1..}n]$ in level order: the root at $A[1]$, then its two children, then their four children, and so on. With $1$-based indexing the navigation is pure arithmetic, no pointers required:

Doubling an index walks down to a left child; halving walks back up to a parent. On a machine these are single shift operations, which is part of why heaps are fast in practice. Here is a small max-heap shown both as a tree and as the array that actually lives in memory:

Read level by level, the array is

The blue numbers below trace the correspondence: each tree node $i$ lives at array slot $i$, so doubling the index ($2i$, $2i+1$) steps down to a child and halving ($\lfloor i/2\rfloor$) steps back up to the parent.

Check the index rule on $A[2]=14$: its children are at $A[4]=8$ and $A[5]=7$, both smaller, and its parent is at $A[1]=16$, larger. The largest key always sits at the root, $A[1]$. A heap on $n$ nodes is complete, so its height, the number of edges on the longest root-to-leaf path, is $\lfloor {\log }_{2}n\rfloor =\Theta (\log n)$. Every operation below costs at most one such trip up or down the tree.

A heap is not a sorted array: it is far weaker, ordering only along ancestor-descendant paths, with no relation between siblings or cousins. That weakness is exactly why a heap is cheap to maintain.

Sift-down: restoring the property at one node

The single primitive every heap operation rests on is $\text{Max-Heapify}$. It assumes the subtrees rooted at the two children of $i$ are already max-heaps, but $A[i]$ itself may be smaller than a child and thus violate the property. It repairs the violation by floating $A[i]$ down to its rightful level, a motion usually called sift-down.²

We compare $A[i]$ against both children, find the largest of the three, and, if a child wins, swap it up and recurse into the subtree that just received the smaller key. The violation moves strictly down one level each step, so the recursion can run no deeper than the tree is tall: $O(\log n)$ time, $O(1)$ extra space (or $O(\log n)$ stack, trivially made iterative). We track the logical length of the heap in a field $A.heapsize\le A.length$, which lets the array hold heap and non-heap regions side by side, an arrangement central to heapsort below.

Building a heap bottom-up

To turn an arbitrary array into a heap we call $\text{Max-Heapify}$ at every internal node, but in the right order. The leaves $A[\lfloor n/2\rfloor +\mathrm{1..}n]$ are already valid one-element heaps, so we start just above them and work upward to the root. Processing a node only after its children are heaps is exactly the precondition $\text{Max-Heapify}$ demands.

On $n=10$ nodes the leaves are $A[\mathrm{6..10}]$ (already heaps, so we skip them), and we sift down the internal nodes $A[5],A[4],\dots ,A[1]$ in that decreasing order, so that every node is processed only after both of its children are.

The loop invariant makes the correctness immediate.

Initialization: nodes $\lfloor n/2\rfloor +\mathrm{1..}n$ are leaves, hence trivial heaps. Maintenance: the children of $i$ are numbered higher than $i$, so by the invariant they head max-heaps, precisely what $\text{Max-Heapify}(A,i)$ needs, and it extends the property to $i$. Termination: when $i=0$, node $1$ (and all others) roots a max-heap.

Why it is $O(n)$, not $O(n\log n)$

The easy bound is immediate: there are $O(n)$ calls to $\text{Max-Heapify}$, each costing $O(\log n)$, for $O(n\log n)$. That is correct but loose, and the looseness matters. Most nodes are near the bottom of the tree, where $\text{Max-Heapify}$ has almost nothing to do.

A heap of $n$ nodes has at most $\lceil n/2^{h+1}\rceil$ nodes at height $h$, and a sift-down from height $h$ costs $O(h)$. Summing the real work over all heights,

The series ${\sum }_{h\ge 0}h/2^h$ converges to $2$, using the standard identity ${\sum }_{h\ge 0}h{x}^h=x/(1-x{)}^2$ at $x=\frac{1}{2}$. The infinite sum is a constant, so the whole bound collapses to $O(n)$.

The intuition behind the algebra: half the nodes are leaves (zero work), a quarter sit one level up (at most one swap each), an eighth two levels up, and so on. Cost per node falls geometrically as the number of nodes at that level rises geometrically, and the two effects cancel to leave a linear total.³ Building a heap is asymptotically negligible compared to the sort that follows.

Heapsort

A max-heap keeps the largest element at the root, $A[1]$. To sort, we repeatedly move that maximum to where it belongs, the back of the array, then shrink the heap and repair it.

The array splits into two regions: a heap at the front, $A[\mathrm{1..}A.heapsize]$, and a growing sorted suffix at the back. Each iteration swaps the heap's maximum into the slot just before the sorted suffix, drops the heap size by one, and runs a single sift-down from the root to re-establish the max-heap property on the smaller heap. After $n-1$ iterations the heap is a single element, necessarily the global minimum, and $A$ is sorted ascending.

Cost. $\text{Build-Max-Heap}$ is $O(n)$. The loop runs $n-1$ times, each iteration doing $O(1)$ work plus one $\text{Max-Heapify}$ at $O(\log n)$. The total is

and this is the bound in every case, best, average, and worst, because the heap is always full height during the extractions. Heapsort is in place ($O(1)$ auxiliary space beyond the array) but not stable: the swaps scatter equal keys. Compared to its peers it lacks quicksort's cache-friendliness, since the parent/child jumps roam across memory, which is why quicksort usually wins in practice despite the worse worst case. Heapsort's niche is the guaranteed $\Theta (n\log n)$ ceiling with no extra memory, exactly the property introsort borrows as a fallback when quicksort's recursion runs too deep.⁴

Priority queues

Sorting is only the first use of a heap. The same structure implements a priority queue: a set $S$ of elements, each with a key (its priority), supporting

• $\text{Insert}(S,x)$: add $x$ to $S$;
• $\text{Maximum}(S)$: return the element with the largest key;
• $\text{Extract-Max}(S)$: remove and return that element;
• $\text{Increase-Key}(S,x,k)$: raise $x$'s key to $k$.

A max-heap answers Maximum in $O(1)$, since it is just $A[1]$, and supports the mutating operations in $O(\log n)$, the height of the tree.⁵

$\text{Increase-Key}$ moves the other direction: bump a key and sift up, repeatedly swapping with the parent while the heap property is violated, again in $O(\log n)$. Insert is just an $\text{Increase-Key}$ from $-\infty$: append the new element as the last leaf, then sift it up.

Reading heapsort through this lens, it is nothing but $n$ successive $\text{Extract-Max}$ operations, writing each maximum into the vacancy the shrinking heap leaves behind. Priority queues built this way drive Dijkstra's shortest paths, Prim's minimum spanning tree, event-driven simulation, and any scheduler that must repeatedly serve the most urgent task.

Takeaways

• A binary heap is a complete binary tree stored as an array; index arithmetic ($\mathrm{parent}(i)=\lfloor i/2\rfloor$, children $2i$ and $2i+1$) replaces pointers, and the height is $\Theta (\log n)$.
• The max-heap property orders only ancestor over descendant: weak enough to maintain cheaply, strong enough to keep the maximum at the root.
• $\text{Max-Heapify}$ (sift-down) repairs one violation in $O(\log n)$; $\text{Build-Max-Heap}$ applies it bottom-up in $O(n)$, since work falls geometrically while node counts rise geometrically.
• $\text{Heapsort}$ repeatedly extracts the max into the array's tail, sorting in place in $\Theta (n\log n)$ in all cases, though it is unstable and not cache-friendly.
• The same heap is a priority queue: $O(1)$ maximum, $O(\log n)$ insert, extract-max, and increase-key, the operations Dijkstra, Prim, and schedulers are built on.