GATE CS 2015 Set 3 Q19 — Binary Heaps

To find the minimum number of interchanges (swaps) required to convert the given array into a max-heap, we first represent the array as a binary tree where the element at index $i$ has children at indices $2i$ and $2i+1$ (using 1-based indexing):

• Level 0: $89$ (index 1)
• Level 1: $19$ (index 2), $50$ (index 3)
• Level 2: $17$ (index 4), $12$ (index 5), $15$ (index 6), $2$ (index 7)
• Level 3: $5$ (index 8), $7$ (index 9), $11$ (index 10), $6$ (index 11), $9$ (index 12), $100$ (index 13)

Checking the max-heap property ($A[parent] \ge A[child]$), we find only one violation: the node $15$ at index 6 is smaller than its right child $100$ at index 13.

Since $100$ is the largest element in the entire array, it must eventually reach the root (index 1) of the max-heap. We can achieve this by bubbling up $100$ along its ancestor path:

1. Swap 1: Swap $100$ (index 13) with its parent $15$ (index 6).
   Array becomes: $\langle 89, 19, 50, 17, 12, \mathbf{100}, 2, 5, 7, 11, 6, 9, \mathbf{15} \rangle$
2. Swap 2: Swap $100$ (index 6) with its parent $50$ (index 3).
   Array becomes: $\langle 89, 19, \mathbf{100}, 17, 12, \mathbf{50}, 2, 5, 7, 11, 6, 9, 15 \rangle$
3. Swap 3: Swap $100$ (index 3) with its parent $89$ (index 1).
   Array becomes: $\langle \mathbf{100}, 19, \mathbf{89}, 17, 12, 50, 2, 5, 7, 11, 6, 9, 15 \rangle$

The array now satisfies the max-heap property. The minimum number of interchanges required is 3.