Challenge: Convert a Max-Heap to a Min-Heap

If you are given a Max Heap, can you convert it into a Min Heap? A solution is placed in the "solution" section to help you, but we would suggest you try to solve it on your own first.

Problem Statement

In this problem, you have to implement the convertMax() function to convert a Binary Max Heap into a Binary Min Heap. An illustration is also provided for your understanding.

Function Prototype:

void convertMax(int []maxHeap);

Here, maxHeap is an array which is given in maxHeap format, i.e. the parent is greater than its children. It’s a Binary Max Heap, meaning that for a particular node there can be a max. of 2 children (left and right respectively).

Output

It does not return anything. The maxHeap array is manipulated and changed to a min-heap.

Sample Input

[9,4,7,1,-2,6,5];

Sample Output

[-2,1,5,9,4,6,7]

Explanation

In a Binary Min Heap, the parent node has minimum value compared to its children (which could be a maximum of two). In the result array, -2 is the root of the Min Heap, and both of its children have greater value: left child 1 (calculated as (index∗2)+1(index * 2) +1) and right child 5 (calculated as (index∗2)+2(index * 2) +2).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.