Question

6.3-2
Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from
(A.length/2] to 1 rather than increase from 1 to [A.length/2]?​

Answer 1

Answer:

Step-by-step explanation:

Our aim is to understand why do we want it to decrease instead of increase.

Assuming that A[i]: A[left(i)] and A[right(i)] are the two Max heaps, we conclude that Max-Heapify(A, i) works.

We can say that leaf nodes are Max heaps too, since we get A[x] such that x > n divided by 2.

So Going in reverse order A[n/2] is the first non leaf node, i.e. the sub-trees rooted at all nodes A[y] : 1<= y <= n/2 might not be max heaps and therefore MAX_HEAPIFY must be performed on each of them.

Looping in reverse order ensures that the children of a node are heapified before the node and therefore the necessary requirement for MAX-HEAPIFY to work is fulfilled for each node.

It does not need to be true for every node, like max heap, for the assumption for MAX-HEAPIFY() to work, since we loop from 1 to n/2.

Hence in order to BUILD-MAX-HEAPIFY work correctly we need to reverse the loop.

I hope this helps your studies! Keep it up!