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.
We'll cover the following
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 ) and right child 5 (calculated as ).
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.