Why do we want the loop index \(i\) in line 2 of BUILD-MAX-HEAP to decrease from \(\lfloor A.length / 2 \rfloor\) to \(1\) rather than increase from \(1\) to \(\lfloor A.length / 2 \rfloor\)?

Reversing the order of the BUILD-MAX-HEAP procedure violates the loop invariant that states each node with a higher index than \(i\) is the root of a max heap.

Suppose we used this new order on the heap from Exercise 6.3-1. Acting upon \(A[1]\) would result in shifting the value \(5\) to a leaf node on the right side. This is a different location for the node, but doesn’t seem problematic. Acting on \(A[2]\) however, would result in a swap such that \(A[2] = 84\), but thanks to our first swap we have \(A[1] = 17\) and so \(A[1] < A[2]\) and the max heap property is violated.

Thus to use this alternative ordering, we would need to expand our procedure to call MAX-HEAPIFY on parent elements of \(i\), drastically and unnecessarily increasing the runtime of BUILD-MAX-HEAP.