In this bottom-up heapify loop, why must sift-down run from the last internal node toward index 0?

## What the loop is doing The bottom-up build repairs an arbitrary array into a heap with one backwards sweep. The whole algorithm is a loop and a helper: ``` build_max_heap(a): n = length(a) for i in n/2 - 1 .. 0 step -1: // last internal node, back to the root sift_down(a, i, n) ``` Everything about its correctness lives in the loop's direction and its start index. ## The precondition of sift-down Sift-down repairs a subtree whose root may be out of place but whose two child subtrees are **already valid heaps**. Under that assumption, exchanging the root with its stronger child, and repeating one level lower, is enough: the new root out-ranks both children, and the only subtree that could have been damaged is the one the displaced element fell into, which the loop then continues to fix. Strip the assumption away and the reasoning collapses. If the child subtrees are still unrepaired, a node can be pushed past a child that is itself out of place, and nothing later in the pass revisits it. ## Why decreasing index order satisfies that precondition In the implicit array layout a node at index `i` has its children at `2i + 1` and `2i + 2` — both strictly greater than `i`. So "every descendant has a larger index than its ancestor" is a structural fact, and iterating `i` downwards is exactly a bottom-up traversal: by the time the loop reaches `i`, every index above `i` has been processed, which includes both of `i`'s subtrees in their entirety. The loop invariant is "every subtree rooted at an index greater than `i` is a valid heap", it holds trivially when the loop starts, sift-down preserves it, and when `i` reaches 0 it says the whole array is a heap. ## Why the start index is n/2 - 1 Every index from `n/2` to `n - 1` is a leaf: a node at index `i` has a left child only if `2i + 1 < n`. A single node is already a valid heap, so calling sift-down on it is a guaranteed no-op. Starting at `n - 1` instead is therefore **not a correctness bug** — it is a waste of about n/2 no-op calls, and the build still produces the right answer in linear time. Candidates who confidently answer "the heap comes out corrupted" have not thought it through; the honest answer is "nothing breaks, you just burned half your iterations." ## What reversing the loop actually produces This one *is* a correctness bug, and it is worth having a concrete case ready. Take seven pending payments with urgency scores in ascending order, `[1, 2, 3, 4, 5, 6, 7]`, and build a max-heap where the most urgent payment belongs at the root. **Correct pass** (`i = 2, 1, 0`): - `i = 2`: 3 loses to child 7, swap -> `[1, 2, 7, 4, 5, 6, 3]` - `i = 1`: 2 loses to child 5, swap -> `[1, 5, 7, 4, 2, 6, 3]` - `i = 0`: 1 loses to child 7, swap -> `[7, 5, 1, 4, 2, 6, 3]`, then continues at index 2 where 1 loses to 6 -> `[7, 5, 6, 4, 2, 1, 3]` Result `[7, 5, 6, 4, 2, 1, 3]`: valid, and the most urgent item, 7, is at the root. **Reversed pass** (`i = 0, 1, 2`): - `i = 0`: 1 loses to 3, swap, then continues down and loses to 7 -> `[3, 2, 7, 4, 5, 6, 1]` - `i = 1`: 2 loses to 5, swap -> `[3, 5, 7, 4, 2, 6, 1]` - `i = 2`: 7 out-ranks both children, stop Result `[3, 5, 7, 4, 2, 6, 1]`. The root holds 3 while its own child holds 5, so the invariant is broken at the very top, and the most urgent payment, 7, is not the one that would be dispatched first. The failure is silent: no crash, no exception, just a dispatch queue that hands back the wrong record. ## The other variant people write Sweeping `i` from 1 up to `n - 1` and calling **sift-up** on each is a third thing, and it is correct — but it is precisely the repeated-insertion build in disguise, at `O(n log n)`. That is the pairing to keep straight: sift-down must go bottom-up, sift-up must go top-down, and mixing the direction with the operation is where the bug lives. ## Testing for it The reversed-loop bug survives small hand tests, because on three or four elements a top-down pass often does produce a valid heap by luck. Verify the invariant across every index for randomly generated arrays of a few dozen elements, and assert that the extracted sequence is non-increasing rather than only checking the first element.