Why do we want the loop index \(i\) in line 2 of \(\textsc{Build-Max-Heap}\) to decrease from \(\lfloor A.length/2 \rfloor\) to 1 rather than increase from 1 to \(\lfloor A.length/2 \rfloor\)?
The fundamental reason is that \(\textsc{Max-Heapify}\) has a crucial precondition: it assumes that the binary trees rooted at the left and right children of node \(i\) are already max-heaps. By iterating downward from \(\lfloor n/2 \rfloor\) to 1, we process nodes in a bottom-up fashion. This ensures that whenever we call \(\textsc{Max-Heapify}(A, i)\), both subtrees of node \(i\) have already been processed and are valid max-heaps, satisfying the precondition.
What Happens with the Correct Order (Decreasing)
When we start at \(i = \lfloor n/2 \rfloor\) and move downward:
-
First nodes processed: These are nodes just above the leaves. Their children are all leaves, which are trivially max-heaps (single elements always satisfy the heap property).
-
Higher nodes: By the time we process node \(i\), we’ve already processed all nodes at higher indices (which are descendants of \(i\)). Therefore, both subtrees rooted at \(i\)’s children are guaranteed to be max-heaps.
-
Loop invariant maintained: At the start of each iteration, all nodes \(i+1, i+2, \ldots, n\) are roots of max-heaps.
What Goes Wrong with Incorrect Order (Increasing)
If we were to iterate upward from 1 to \(\lfloor n/2 \rfloor\), we would violate \(\textsc{Max-Heapify}\)’s precondition:
-
Root processed first: We would call \(\textsc{Max-Heapify}(A, 1)\) when the subtrees rooted at indices 2 and 3 are not yet max-heaps.
-
Broken assumption: \(\textsc{Max-Heapify}\) might correctly place the root value among itself and its two children, but it cannot fix violations deeper in the tree because those deeper nodes haven’t been processed yet.
-
Invalid result: After the loop completes, we would have no guarantee that the array represents a valid max-heap.