Consider the following array of elements. $$\langle 89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100 \rangle$$ The minimum number of interchanges needed to convert it into a max-heap is

Consider the 1-indexed array of size $n = 13$:

To build a max-heap using standard bottom-up heap construction, we run MAX-HEAPIFY on internal nodes from index $i = \lfloor n/2 \rfloor = 6$ down to $1$:

1. At index 6 (value 15):

   • Left child is at index $12$ (value $9$).

   • Right child is at index $13$ (value $100$).

   • The maximum among $\{15, 9, 100\}$ is $100$ at index 13.

   • Interchange 1: Swap $A[6]$ and $A[13]$.

   • Array becomes: $[89, 19, 50, 17, 12, \mathbf{100}, 2, 5, 7, 11, 6, 9, \mathbf{15}]$

2. At indices 5, 4:

   • Index 5 (value 12) with children index 10 (value 11) and index 11 (value 6): satisfies max-heap property (no swap).

   • Index 4 (value 17) with children index 8 (value 5) and index 9 (value 7): satisfies max-heap property (no swap).

3. At index 3 (value 50):

   • Left child is at index $6$ (value $100$).

   • Right child is at index $7$ (value $2$).

   • The maximum is $100$ at index 6.

   • Interchange 2: Swap $A[3]$ and $A[6]$.

   • Array becomes: $[89, 19, \mathbf{100}, 17, 12, \mathbf{50}, 2, 5, 7, 11, 6, 9, 15]$

   • At index 6 (value 50), children are index 12 (value 9) and index 13 (value 15), which satisfies the max-heap property.

4. At index 2 (value 19):

   • Children are index 4 (value 17) and index 5 (value 12): satisfies max-heap property (no swap).

5. At index 1 (value 89):

   • Left child is at index $2$ (value $19$).

   • Right child is at index $3$ (value $100$).

   • The maximum is $100$ at index 3.

   • Interchange 3: Swap $A[1]$ and $A[3]$.

   • Array becomes: $[\mathbf{100}, 19, \mathbf{89}, 17, 12, 50, 2, 5, 7, 11, 6, 9, 15]$

   • At index 3 (value 89), children are index 6 (value 50) and index 7 (value 2), which satisfies the max-heap property.

Total number of interchanges required = 3.

Hence, the correct option is (D).