A tree stored in an array with no pointers at all, sorting in Θ(n lg n) worst case and in place, and doubling as the priority queue you will actually use.
Heapsort combines the best of the two sorts so far: it runs in Θ(n lg n) like merge sort, and it sorts in place like insertion sort, using only a constant amount of extra storage. It gets there by way of the heap, the first genuine data structure in the book. The heap is worth more than the sort it enables — it is the standard implementation of a priority queue, which shows up in Dijkstra’s algorithm, Prim’s algorithm, event simulation, and every scheduler you have ever used.
HEAP-MAXIMUM is now MAX-HEAP-MAXIMUM, HEAP-EXTRACT-MAX is MAX-HEAP-EXTRACT-MAX, and so on, making the max/min variant explicit everywhere. Array length is passed explicitly. The 4th edition also adds a discussion of building a heap by repeated insertion versus BUILD-MAX-HEAP.Two attributes describe a heap array A:
A.length — the number of elements in the array.A.heap-size — how many of them are part of the heap. Always 0 ≤ A.heap-size ≤ A.length.The distinction matters in heapsort, where the tail of the array holds already-sorted output that is no longer part of the heap. Only A[1 : A.heap-size] obeys the heap property.
With 1-based indexing, the parent and children of a node are pure arithmetic:
PARENT(i) return ⌊i/2⌋
LEFT(i) return 2i
RIGHT(i) return 2i + 1On a real machine LEFT is a one-bit left shift, RIGHT is a shift plus one, and PARENT is a right shift. Most implementations inline all three.
There are two flavours, differing only in the direction of the inequality:
| Kind | Property, for every node i other than the root | Root holds | Used for |
|---|---|---|---|
| Max-heap | A[PARENT(i)] ≥ A[i] | The largest element | Heapsort, max-priority queues |
| Min-heap | A[PARENT(i)] ≤ A[i] | The smallest element | Min-priority queues: Dijkstra, Prim, schedulers |
O(1) and nothing else quickly; it cannot do ordered traversal or search for an arbitrary key in better than Θ(n). That is the trade for the cheap representation.Height. The height of a node is the number of edges on the longest downward path to a leaf; the height of the heap is the height of its root. Since the tree is nearly complete with n nodes, its height is ⌊lg n⌋, that is Θ(lg n). Every heap operation walks one root-to-leaf path, so every one costs O(lg n).
Two counting facts used in the analyses below:
⌊n/2⌋+1, ⌊n/2⌋+2, …, n. So more than half of all nodes are leaves.n-element heap has at most ⌈n/2h+1⌉ nodes of height h. Nodes get scarcer as they get taller, which is exactly why BUILD-MAX-HEAP is linear.The workhorse. MAX-HEAPIFY(A, i) assumes the binary trees rooted at LEFT(i) and RIGHT(i) are already max-heaps, but A[i] may be smaller than its children, violating the property at i alone. It floats A[i] down to its correct place.
MAX-HEAPIFY(A, i)
1 l = LEFT(i)
2 r = RIGHT(i)
3 if l ≤ A.heap-size and A[l] > A[i]
4 largest = l
5 else largest = i
6 if r ≤ A.heap-size and A[r] > A[largest]
7 largest = r
8 if largest ≠ i
9 exchange A[i] with A[largest]
10 MAX-HEAPIFY(A, largest)Find the largest of the node and its two children. If it is not the node itself, swap and recurse into the subtree that received the smaller value.
MAX-HEAPIFY sifting a small value down. The violation never disappears, it only moves one level lower each step, until it reaches a leaf.Running time. Constant work per node plus one recursive call on a subtree. The worst case is when the last row is exactly half full, which makes a child’s subtree as large as 2n/3. So
T(n) ≤ T(2n/3) + Θ(1) → T(n) = O(lg n) // master case 2Equivalently and more simply: the recursion follows one path from node to leaf, and paths have length O(lg n). For a node of height h, the cost is O(h) — a sharper statement we need next.
To turn an arbitrary array into a heap, call MAX-HEAPIFY on every non-leaf node, working bottom-up.
BUILD-MAX-HEAP(A, n)
1 A.heap-size = n
2 for i = ⌊n/2⌋ downto 1
3 MAX-HEAPIFY(A, i)Start at ⌊n/2⌋ because everything past it is a leaf, and a single node is already a heap. Go downto 1 so that when MAX-HEAPIFY(A, i) runs, both its child subtrees are already heaps — which is precisely its precondition.
for loop, each node i+1, i+2, …, n is the root of a max-heap. Initialization holds because those are all leaves; maintenance holds because MAX-HEAPIFY’s precondition is met; at termination i = 0, so node 1 is the root of a max-heap.O(n) boundThe easy analysis says: n/2 calls, each O(lg n), so O(n lg n). That is correct but not tight, and the tight bound is one of the prettiest small results in the book.
The point is that MAX-HEAPIFY on a node of height h costs O(h), not O(lg n) — and most nodes are short. There are at most ⌈n/2h+1⌉ nodes of height h, so:
Total = ∑ from h=0 to ⌊lg n⌋ of ⌈n/2h+1⌉ · O(h)
= O( n · ∑ from h=0 to ∞ of h/2h )
= O( n · 2 ) // the series converges to 2
= O(n)Height h | Nodes at that height | Cost each | Level total |
|---|---|---|---|
| 0 (leaves) | ≈ n/2 | 0 | 0 |
| 1 | ≈ n/4 | 1 | n/4 |
| 2 | ≈ n/8 | 2 | n/4 |
| 3 | ≈ n/16 | 3 | 3n/16 |
lg n (root) | 1 | lg n | lg n |
The expensive calls are rare and the common calls are cheap, and the geometric decay wins. Building a heap is linear, not n lg n.
MAX-HEAP-INSERT n times. That is O(n lg n), and the bound is tight — insertion sifts up from a leaf, and since most nodes are leaves, most insertions can travel the full height. Bottom-up building sifts down from a node, and most nodes are near the bottom with nowhere to go. Same tree, opposite direction, different complexity. The 4th edition makes this comparison explicit.With a max-heap the largest element sits at A[1], and the last slot A[n] is where the largest element belongs in sorted order. Swap them, shrink the heap by one so the placed element is frozen, restore the heap property at the root, and repeat.
HEAPSORT(A, n)
1 BUILD-MAX-HEAP(A, n)
2 for i = n downto 2
3 exchange A[1] with A[i] // biggest goes to its final slot
4 A.heap-size = A.heap-size - 1 // freeze it out of the heap
5 MAX-HEAPIFY(A, 1) // restore the property at the rootA[1 : heap-size] is a max-heap; A[heap-size+1 : n] holds the largest elements in their final sorted positions.Running time. BUILD-MAX-HEAP costs O(n); the loop runs n-1 times, each iteration doing O(1) work plus one MAX-HEAPIFY at O(lg n). Total O(n lg n), and it is Θ(n lg n) in the worst case. Extra space is O(1).
Heapsort is a fine algorithm that is rarely the fastest choice in practice. The heap, on the other hand, is everywhere — because it is the standard implementation of a priority queue.
S of elements, each with an associated key. A max-priority queue supports INSERT, MAXIMUM, EXTRACT-MAX, and INCREASE-KEY. A min-priority queue is the mirror image, and is the one graph algorithms use.MAX-HEAP-MAXIMUM(A)
1 if A.heap-size < 1
2 error "heap underflow"
3 return A[1]Θ(1). The maximum is always at the root, by the heap property.
MAX-HEAP-EXTRACT-MAX(A)
1 max = MAX-HEAP-MAXIMUM(A)
2 A[1] = A[A.heap-size] // move the last leaf to the root
3 A.heap-size = A.heap-size - 1
4 MAX-HEAPIFY(A, 1) // sift it back down
5 return maxO(lg n), dominated by the single MAX-HEAPIFY. Note the pattern: overwrite the root with the last leaf, shrink, sift down. That is the same move as line 3-5 of heapsort.
MAX-HEAP-INCREASE-KEY(A, x, k)
1 if k < x.key
2 error "new key is smaller than current key"
3 x.key = k
4 find the index i of x in array A
5 while i > 1 and A[PARENT(i)].key < A[i].key
6 exchange A[i] with A[PARENT(i)]
7 i = PARENT(i)O(lg n). This one sifts up, not down: the node got bigger, so it may now exceed its parent. The loop walks from the node toward the root, exactly like insertion sort’s inner loop walking a value into place.
MAX-HEAP-INSERT(A, x, n)
1 if A.heap-size == n
2 error "heap overflow"
3 A.heap-size = A.heap-size + 1
4 k = x.key
5 x.key = -∞ // place a dummy at the new leaf
6 A[A.heap-size] = x
7 MAX-HEAP-INCREASE-KEY(A, x, k) // then raise it to its real keyO(lg n). Insert at the first free leaf with key -∞ (which can never violate the property), then increase it to the true key and let the sift-up place it.
x in A” is Θ(n) if you scan. Real implementations store a handle inside each element that records its current array index and update it on every swap. Dijkstra’s algorithm in Chapter 22 needs DECREASE-KEY on arbitrary vertices, so it depends on this bookkeeping; without it the O(lg n) claim is false.| Operation | Direction | Cost | Why |
|---|---|---|---|
MAXIMUM | — | Θ(1) | Read the root |
EXTRACT-MAX | Sift down | O(lg n) | One root-to-leaf path |
INCREASE-KEY | Sift up | O(lg n) | One node-to-root path |
INSERT | Sift up | O(lg n) | Add a leaf, then increase-key |
BUILD from n items | Sift down | Θ(n) | Most nodes are short |
| Insertion sort | Merge sort | Heapsort | |
|---|---|---|---|
| Worst case | Θ(n²) | Θ(n lg n) | Θ(n lg n) |
| Best case | Θ(n) | Θ(n lg n) | Θ(n lg n) |
| Extra space | Θ(1) | Θ(n) | Θ(1) |
| Stable | Yes | Yes | No |
| Memory access | Sequential | Sequential | Scattered |
| Adaptive to sorted input | Yes | No | No |
Θ(n lg n) worst case and O(1) space, which makes it the safe default when you must guarantee both. But its memory access pattern jumps by factors of two through the array, so it thrashes the cache that the RAM model pretends does not exist. Quicksort, whose worst case is worse, beats it in practice by a wide margin. The common compromise is introsort: run quicksort, and if the recursion depth exceeds 2 lg n, switch to heapsort to guarantee the bound. You get quicksort’s speed with heapsort’s safety net.PARENT(i) = ⌊i/2⌋, LEFT(i) = 2i, RIGHT(i) = 2i+1.A[PARENT(i)] ≥ A[i]. It constrains parents against children only — siblings are unordered, so a heap is neither sorted nor a search tree.⌊lg n⌋. More than half the nodes are leaves, and there are at most ⌈n/2h+1⌉ nodes of height h.MAX-HEAPIFY sifts one value down a single root-to-leaf path: O(lg n), or O(h) for a node of height h.BUILD-MAX-HEAP is Θ(n), not Θ(n lg n) — go bottom-up from ⌊n/2⌋ downto 1, and the series ∑ h/2ᵗ converges to 2. Building by repeated insertion really is Θ(n lg n), because sifting up starts where the nodes are.Θ(n lg n) worst case, O(1) space, not stable.MAXIMUM is Θ(1); EXTRACT-MAX, INSERT, and INCREASE-KEY are O(lg n). Extract sifts down, insert and increase-key sift up.INCREASE-KEY needs to locate the element, so real implementations keep an index handle in each element. Dijkstra and Prim depend on it.Chapter 7 gives quicksort, the algorithm that wins in practice despite a Θ(n²) worst case. Its analysis is the first serious payoff from Chapter 5: randomizing the pivot choice gives an expected Θ(n lg n) running time on every input, proved with indicator random variables. Chapter 8 then shows that Ω(n lg n) is a hard floor for any comparison sort, and how to get underneath it by not comparing.