Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7,…

Key idea: Build the max-heap using bottom-up heapify (sift-down) starting from the last non-leaf node and count each swap.

Initial array: 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉

1. Heapify at index 6 (value 15): children are 9 (index 12) and 100 (index 13). Swap 15 with 100 (indices 6 and 13). Swaps so far: 1.

2. Array becomes: 〈89, 19, 50, 17, 12, 100, 2, 5, 7, 11, 6, 9, 15〉. No further sift-down needed at index 13.

3. Heapify at index 5 (value 12): children 11 and 6 are smaller, so no swap.

4. Heapify at index 4 (value 17): children 5 and 7 are smaller, so no swap.

5. Heapify at index 3 (value 50): children are 100 (index 6) and 2 (index 7). Swap 50 with 100 (indices 3 and 6). Swaps so far: 2.

6. Array becomes: 〈89, 19, 100, 17, 12, 50, 2, 5, 7, 11, 6, 9, 15〉. No further sift-down needed at index 6.

7. Heapify at index 2 (value 19): children 17 and 12 are smaller, so no swap.

8. Heapify at index 1 (value 89): children are 19 (index 2) and 100 (index 3). Swap 89 with 100 (indices 1 and 3). Swaps so far: 3.

9. Final array (max-heap): 〈100, 19, 89, 17, 12, 50, 2, 5, 7, 11, 6, 9, 15〉.

Final conclusion: The minimum number of interchanges required to convert the given array into a max-heap is 3.