GATE CS 1996 Q2.11 — Binary Heaps

To convert the array into a max-heap, we represent it as a complete binary tree using 1-based indexing:

Array: $[89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70]$

The tree representation and the heapification process (starting from the last non-leaf node at index $\lfloor 13/2 \rfloor = 6$) is as follows:

1. Node 6 (value 10): Its children are at index 12 (value 9) and index 13 (value 70). Since $70 > 10$, we swap 10 and 70.
   Interchange 1: Swap $10 \leftrightarrow 70$.
   The array becomes: $[89, 19, 40, 17, 12, \mathbf{70}, 2, 5, 7, 11, 6, 9, \mathbf{10}]$.
2. Node 5 (value 12): Children are 11 and 6. Already satisfies the max-heap property ($12 \ge 11$ and $12 \ge 6$).
3. Node 4 (value 17): Children are 5 and 7. Already satisfies the max-heap property ($17 \ge 5$ and $17 \ge 7$).
4. Node 3 (value 40): Children are index 6 (now value 70) and index 7 (value 2). Since $70 > 40$, we swap 40 and 70.
   Interchange 2: Swap $40 \leftrightarrow 70$.
   The array becomes: $[89, 19, \mathbf{70}, 17, 12, \mathbf{40}, 2, 5, 7, 11, 6, 9, 10]$.
   The sub-tree at index 6 with value 40 and children 9 and 10 is already a valid max-heap ($40 \ge 9$ and $40 \ge 10$).
5. Node 2 (value 19): Children are 17 and 12. Already satisfies the max-heap property ($19 \ge 17$ and $19 \ge 12$).
6. Node 1 (value 89): Children are 19 and 70. Already satisfies the max-heap property ($89 \ge 19$ and $89 \ge 70$).

Thus, the minimum number of interchanges needed to convert the array into a max-heap is 2.