The minimum number of interchanges needed to convert the array 89, 19, 40, 17,…
1996
The minimum number of interchanges needed to convert the array 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70 into a heap with the maximum element at the root is:
- A.
0
- B.
1
- C.
2
- D.
3
Attempted by 49 students.
Show answer & explanation
Correct answer: C
In the array representation of a max-heap, every parent must be greater than or equal to its children. The only violation is on the path 40 -> 10 -> 70: node 10 has child 70, so the heap property fails. First swap 70 with 10, giving the path 40 -> 70 -> 10. Now 70 is still greater than its parent 40, so swap 70 with 40. The path becomes 70 -> 40 -> 10, and all parent-child relations satisfy the max-heap property. Hence the minimum number of interchanges is 2.