Motivation
A sorted array records the order of every pair of keys. A heap records less: each parent dominates its children, making the largest key easy to find without sorting the rest. That partial order supports repeated extraction and a sorting algorithm that uses the input array itself for storage.
The surprising cost is construction. Sifting down one vertex may take logarithmic time, but building a heap at every vertex is linear rather than logarithmic times the number of vertices. Most vertices are close to leaves and have little distance to travel. The proof counts how many vertices can have each height instead of charging all of them the root's worst-case height.
All bounds count constant-cost key comparisons and ordinary array accesses; more expensive key representations require their comparison cost to be included.
Definitions
Definition 8.2.1
(Array shape and max-heap order)
A heap of size occupies array positions one through in the complete binary-tree shape: the children of position are and when within the size bound, and a nonroot parent is . The array is filled level by level from left to right.
A max-heap satisfies on every parent-child pair, comparing keys only. A vertex's height is the largest number of edges from it to a descendant leaf. Leaves have height zero. The root has height at most when .
The active heap may be only a prefix of a longer array; children beyond its current size are ignored even if the array positions exist. Records can carry identity labels besides their keys. A stable sort preserves the original relative order of records with equal keys, a condition separate from numerical sortedness.
Definition 8.2.2
(Iterative sift-down)
Assume the two child subtrees of a chosen position are already heaps. Compare the roots of its existing child subtrees and choose a largest one. If that child's key exceeds the current key, swap them and continue at the child's position. Otherwise stop. Stop as well at a leaf. When child keys tie, either fixed choice is valid. Every step refers to the current active heap bound.
A sift-down implementation can hold its current index, chosen child index and one temporary record in constant auxiliary space. A recursive version would additionally use its call stack; the constant-space sorting statement below uses this iterative routine.
Theorem/Proposition
Theorem 8.2.3
(Sift-down repairs a single root violation)
Under the stated child-subtree hypothesis, sift-down produces a heap on the entire chosen subtree and preserves its multiset of records. It uses work for starting height , with at most two key comparisons per tested level and no more than downward swaps.
Theorem 8.2.4
(Bottom-up heap construction is linear)
For an array of records, apply sift-down at positions in that order. The result is a max-heap. Total construction time is , because
for nonempty input. An empty array needs no sifting and is already a heap.
Theorem 8.2.5
(Heapsort sorts in place with a fixed suffix)
Build a max-heap on the full input. For active sizes , swap the root with position , reduce the active bound to , and sift down the new root. The final array is sorted in nondecreasing key order and has the same records as the input.
Its worst-case time is over distinct-key inputs as grows, and its iterative implementation uses auxiliary space beyond the input array. It is generally unstable. The empty and one-record cases perform no extraction loop.
The unusual-looking storage advantage needs only one array and a changing active-prefix boundary. It is not a claim that the key values fit in one machine word regardless of encoding. Distinct records with equal keys may move, even when the comparison order is already valid.
Proof sketch or proof idea
Proof
(Correctness and cost of sift-down)
For sift-down, a heap root dominates its whole subtree by transitivity along parent-child chains. Therefore the largest child root dominates every key in that child's subtree and also the other child root if there is one. If the current key dominates both roots, all parent-child constraints hold and the procedure stops correctly.
Otherwise swap with a largest child. The new top key dominates the old current key and both former child subtrees. All constraints above the moved-down record are now correct; only that record's new position might violate the order below it. Its own child subtrees were unaffected and remain heaps, so the same argument repeats. The current index strictly descends at each swap, giving at most the starting height many swaps. At a stopping position or leaf, the remaining violation disappears. Swaps preserve the records exactly.
Each tested level needs at most one child-child comparison and one comparison with the current key. A final no-swap test still occurs above a leaf and fits within the original height bound. This proves the cost estimate, including the constant loop setup when height is zero.
Proof
(Why decreasing-index construction is linear)
For construction, every leaf is a heap before any work. At index in decreasing order, its children's positions are larger, so they have either already been processed or were leaves. Sift-down's hypothesis therefore holds, and induction makes every processed subtree a heap. The final root step covers the whole tree.
To count work, a vertex at index with height at least has a descendant at least , so it must satisfy . Thus at most vertices have such height. Summing the height indicators gives the displayed identity, and the geometric upper bound is less than . The extra constant work per processed vertex is also linear. This proof uses the complete array-tree shape; it does not apply the same vertex-count estimate to an arbitrary unbalanced binary tree.
Proof X-ray
Construction sums different heights, not one common worst case
The key move is to reverse the order of summation: instead of asking how far each vertex can sink, ask how many vertices can sink at least levels. The complete array shape is used exactly once, to get for such a vertex; the decreasing index order is used only to supply sift-down's hypothesis that both child subtrees are already heaps. Nothing else about the keys matters.
The shape hypothesis cannot be dropped from the counting step. In a binary tree that is a single path of vertices the heights are and their sum is , which is quadratic. Multiplying every vertex by the root's logarithmic bound is a valid but loose upper bound, and it misses the linear guarantee that only the balanced shape supplies.
Proof
(Heapsort invariant and running time)
For heapsort, maintain that the active prefix is a heap and the suffix is sorted, with every active key at most every suffix key. Initially the suffix is empty and construction supplies the heap. The root is a maximum of the active records. Exchanging it with the active last position extends the suffix by that maximum, no larger than any already fixed suffix key. Removing that position preserves the complete-tree shape of the prefix, and only its new root can violate heap order. Sift-down repairs it. Induction proves all steps, and the final one-record prefix completes sortedness. Record preservation follows from swaps throughout.
Construction costs linear time, and each of at most extraction steps costs , giving the upper bound. For a comparison sort on distinct keys, a binary decision tree must distinguish all possible relative orders. Its worst depth is at least , which is because the largest half of the factors are at least . The already proved correctness makes heapsort subject to that bound, yielding the stated worst-case order. This does not imply every equal-key input takes that long.
Priority-queue operations and allocation assumptions
The heap root gives a maximum in constant time. To insert with available array capacity, append the new record and swap it upward while larger than its parent. Only that ancestor chain can have a new violation; swapping fixes its lower edge and moves the possible violation toward the root. The chain has logarithmic length. To remove the maximum, replace the root by the last record, shorten the heap and, if any records remain, sift down its root; the child subtrees remain heaps. These give logarithmic worst-case comparison/access costs when storage is already available.
Growing a backing array may separately copy all records. The preceding bound does not make that copy disappear. A doubling array has the separate amortized guarantee proved earlier, while a particular resizing insertion may still have linear physical work. The fixed-size heapsort array needs no such growth, which is why its auxiliary-space and per-extraction analysis are unaffected.
Worked examples
Worked example 8.2.6
(Bottom-up construction on six keys)
Start from . Position three already dominates its only child. Sifting position two swaps one with five, giving . At the root, swap three with six and then with four at its new position. The result is .
The sibling keys five and four need not be sorted against each other in any specified direction; each is constrained only by its own parent and children. The resulting array is a heap because all five parent-child inequalities hold, not because reading the array yields sorted order.
Worked example 8.2.7
(The sorted suffix grows while the active prefix changes)
From that heap, exchange six with the final three. The active prefix becomes and the fixed suffix is six. Sift-down gives active prefix . Next exchange five with the active last two and shorten again; sifting gives followed by suffix .
The suffix must be excluded from child tests. Its large keys are already in their final positions; allowing them back into the active heap would undo the progress invariant. The active root four is now the largest remaining key, not the largest key in the entire array.
Worked example 8.2.8
(Insertion and extraction move along one root path)
Insert seven into heap with capacity available. It appends at position seven, swaps with parent four at position three, then with root six. The heap becomes .
Removing seven moves the last four to the root and shortens the heap to six. Swapping that four with child six yields again. Other branches keep their heap inequalities throughout. Finding and repairing one ancestor or descendant path is enough because the state before the operation was already a heap.
Concept lensStructural
A heap stores only the comparisons needed for its next question
Parent-child order makes the maximum accessible while leaving most sibling and cousin comparisons undecided. Repeated extraction gradually settles a total output order. The complete shape controls operation depth, and the partial key order controls which record may be extracted; neither property alone supplies the algorithm.
Common mistakes
Counterexample mode
Equal-key records can be reversed by the final swap
Take two records in that input order. Heap construction leaves them in place because their keys tie. The sorting extraction still swaps root and last, producing . Keys are correctly sorted but the equal-key identities reverse, so this heapsort is not stable. Stability is a property of record order under ties, not merely of sorted key values.
Common mistake
(Sifting a root whose child subtrees are not yet heaps)
Sift-down compares a record only with its two children, so it repairs a violation at the top and nowhere else. Take , where position two holds one above its children five and four. Sifting position one compares three with the larger child two, finds no violation, and stops, leaving . This is not a heap, because one lies below five. This is why construction must go in decreasing index order: each sift-down then starts with child subtrees that are already heaps.
Common mistake
(Letting sift-down see the sorted suffix)
During heapsort the active bound shrinks, and children beyond it must be ignored. After exchanging the root of with the last active key, the state is . Sifting one down gives . If the routine still used the full array length, it would compare one with its apparent children four and five, and swap it with five. That yields , where the suffix now reads and is no longer sorted.
A heap array need not be globally sorted. Building by repeated insertion has a different cost analysis from bottom-up construction. A recursive sift routine does not have constant call-stack space simply because the array itself is reused. Heap size and allocated array length must remain distinct during sorting and priority-queue updates.
Summary
Sift-down repairs one root after its child subtrees are heaps. Decreasing-index construction satisfies that hypothesis and is linear because total vertex height is linear in a complete tree. Heapsort repeatedly places a maximum into a fixed sorted suffix, with logarithmic extraction work and constant iterative auxiliary storage, while equal-key stability and backing-array allocation retain their separate conditions.
Exercises
Quick check
(A perfect binary tree has height and vertices. Compute the sum of all vertex heights.)
Use the number of vertices with height at least each positive level.
Solution · Answer
For , exactly vertices have height at least . Summing gives . At this is zero, matching the one leaf. The result makes the linear construction sum explicit even when the root height grows.
Quick check
(Give a max-heap array that is sorted in neither increasing nor decreasing order. Explain why every nonincreasing array is nevertheless a max-heap.)
Compare index order with parent-child index relations.
Solution · Answer
The array is a valid max-heap because root five dominates both children. It is not nondecreasing, since five exceeds three, and not nonincreasing, since three is less than four. Conversely in a nonincreasing array, every parent index is smaller than each child index, so its key is at least the child's. All heap inequalities therefore hold. Hence every nonincreasing array is a heap, while the converse fails.
Quick check
(Continue the worked heapsort state with active prefix and sorted suffix until completion. State the active bound at every extraction.)
Do not sift into the fixed suffix.
Solution · Answer
At active size four, swap root four with one, leaving active prefix and suffix . Sift to . At active size three, swap three with two, leaving prefix and suffix ; it is already a heap. At active size two, swap two with one, leaving the single active key one and suffix . The complete array is , and no suffix entry was part of a sift after being fixed.