Question 29

The 1-indexed array of 13 elements is:
A = [89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100].
Internal nodes are at indices $i = \lfloor 13/2 \rfloor = 6$ down to $1$.

Trace bottom-up max-heapify:

1. $i = 6$: $A[6] = 15$. Children are $A[12] = 9$ and $A[13] = 100$. The maximum child is $100$. Swap $A[6]$ and $A[13]$ (1st interchange).
   Array at $i=6$ becomes $100$, and $A[13]$ becomes $15$.
2. $i = 5$: $A[5] = 12$. Children are $A[10] = 11, A[11] = 6$. Both $\le 12$. No interchange.
3. $i = 4$: $A[4] = 17$. Children are $A[8] = 5, A[9] = 7$. Both $\le 17$. No interchange.
4. $i = 3$: $A[3] = 50$. Children are $A[6] = 100, A[7] = 2$. Maximum child is $100$. Swap $A[3]$ and $A[6]$ (2nd interchange).
   $A[3]$ becomes $100$, $A[6]$ becomes $50$. Check subtree at $i=6$: children are $9$ and $15$, both $\le 50$. No further swap.
5. $i = 2$: $A[2] = 19$. Children are $A[4] = 17, A[5] = 12$. Both $\le 19$. No interchange.
6. $i = 1$: $A[1] = 89$. Children are $A[2] = 19, A[3] = 100$. Maximum child is $100$. Swap $A[1]$ and $A[3]$ (3rd interchange).
   $A[1]$ becomes $100$, $A[3]$ becomes $89$. Check subtree at $i=3$: children are $A[6] = 50, A[7] = 2$, both $\le 89$. Subtree satisfied.

The total number of interchanges needed is exactly 3 (Option D).