A batch construction problem
The preceding note describes a min-heap and its individual priority-queue operations. Here the input is an arbitrary array of keys from a totally ordered set; the goal is to rearrange it into a min-heap without losing or duplicating keys. Use a one-indexed array . Children of index are and when those indices are at most . A min-heap requires each parent key to be no greater than each existing child. The empty array and a single-element array already satisfy this property.
Repeatedly inserting all keys can take comparisons. Bottom-up construction instead runs sift-down at indices . Every larger index is a leaf. We use this deterministic convention: choose a smaller child, choose the left child if the two child keys tie, and stop if the parent is already at most that child's key.
Sift-down and its precondition
Definition 3.2.1
(Almost-heap at an index)
The array is an almost-heap at if the subtrees rooted at the existing children of are min-heaps, while the key at itself may be larger than a child key. The height of node is the number of edges on a longest downward path from in the complete array tree.
Sift-down at assumes an almost-heap at . If has no child, stop. Otherwise choose the smaller existing child . If , stop; since is a smallest child, the root is at most both children and the whole subtree is a heap. If , swap those two keys and continue at .
Lemma 3.2.2
(Sift-down repairs an almost-heap)
If the array is an almost-heap at , then sift-down at terminates after at most swaps, leaves the subtree rooted at a min-heap with the same keys, and changes no other position.
Proof
(Moving the possible violation down one level)
Suppose the almost-heap condition holds at the current index and is the smaller child. If no swap happens, the root is at most both children and both child subtrees are heaps, so the subtree is a heap. If and we swap, the old key moves to and the key moves to . Before the swap, is no greater than its own children by the child-heap assumption, and no greater than its sibling by choice. After the swap it is the new root at and is no greater than either child: the moved-down old parent is strictly larger, and the sibling was at least . The untouched child subtree remains a heap. Only the subtree at can violate heap order, and its two child subtrees are still heaps, so the almost-heap condition holds at . The index moves strictly downward, so the process stops after at most swaps, at a leaf or at a valid root. Swaps preserve the multiset of keys and touch only positions in the subtree.
Proof X-ray
Where the child-heap assumption is spent
The assumption that both child subtrees are heaps is used once per swap, to know that the key moving up is at most everything below . The choice of the smaller child is used once, to know that it is also at most its sibling. If either fact failed, the new root at could still be larger than something below it, and a single downward walk would not suffice. The walk terminates because the index strictly increases, and it closes either at a leaf or at a node whose key is already at most its smaller child.
Theorem 3.2.3
(Bottom-up construction is correct)
Processing the indices in decreasing order with sift-down turns any array into a min-heap holding exactly the original keys.
Proof
(Induction over decreasing indices)
Before processing , every child has a larger index and its subtree is already a heap: either it is a leaf, or its own sift-down was completed earlier, and no sift-down since then has changed its subtree, because each changes only the subtree of its own index and no index strictly between and the child is an ancestor of the child. So the array is an almost-heap at . Sift-down therefore makes the subtree rooted at a heap. Induction down to proves that the final array is a min-heap with exactly the original keys. No stability among equal keys is promised.
Counterexample mode
Processing the indices in increasing order
Claim: it does not matter in which order the indices are sifted. Take and sift at in this order. At index , swaps with the smaller child and then with the smaller child of its new position , giving . At index , the key is at most its children and , so nothing happens. At index , swaps with , giving . The root is larger than its child , so the result is not a heap. At index the children's subtrees were not yet heaps, so the precondition failed; decreasing order guarantees it.
Why the build is linear
Theorem 3.2.4
(Linear bound for building a heap)
For , the sum of the heights of all nodes satisfies . Hence bottom-up construction makes fewer than swaps and key comparisons in total.
Proof
(Counting nodes by height)
A sift-down started at makes at most downward swaps. A node has height at least exactly when its leftmost possible descendant at index exists, so there are at most such nodes. Double-counting the possible downward levels gives
The last sum is finite, since the terms eventually vanish. A level uses at most a constant number of key comparisons, and the loop starts at most sifts; therefore the whole build uses comparisons and swaps in a constant-time comparison/access model. For , the loop does nothing.
The input array is reused, so an iterative sift-down uses auxiliary space. This bound is for building a heap, not for producing a fully sorted array.
Worked traces
Worked example 3.2.5
(A seven-key array)
Start with . The last internal index is .
| Processed index | Array after sift-down |
|---|---|
| 3 | |
| 2 | |
| 1 |
At index , key first swaps with , then with . The final root is a minimum, but siblings and subtrees are not generally sorted.
Worked example 3.2.6
(Counting the swaps for n = 7)
The heights of the nodes are , with sum . This agrees with the counting argument: at least one level above the leaves requires index , so three nodes; at least two levels requires , one node; at least three levels requires , none. In the trace above the sift-downs made swaps, so every sift-down used its full height, and the number of swaps equals .
Worked example 3.2.7
(Ties and tiny inputs)
For , only index is internal. The children tie at key , and the left-child rule picks index ; since we swap, giving . Picking the right child instead would give ; both are heaps. For , index has the single child at index , and gives . For or there is no internal index and the array is unchanged.
Common mistake
(Reading the heap as a sorted array)
The result of the first trace is a valid heap, but it is not sorted: even though is at position . A heap guarantees only that each key is at most its children, so only the root is known to be a minimum. Producing sorted output needs further work.
Exercises
Quick check
(Apply the stated convention to . Give the array after processing indices , and .)
Index has only the child at index .
Solution · Answer
The successive arrays are , , and .
Quick check
(Build a heap from using the left-child tie rule. Why does changing the tie rule preserve correctness even if the resulting array changes?)
Compare the two tied children as candidates.
Solution · Answer
The result is . Either tied child is a smallest child, so the local heap argument still applies; the ordering of equal keys need not be stable.
Quick check
(Explain why bounding each sift separately by proves only , and identify the additional fact that gives the sharper bound.)
How many nodes are tall?
Solution · Answer
That estimate charges every node the maximum possible height. There are at most nodes of height at least , so summing the actual height bounds gives fewer than downward levels in total.