Convert Max Heap to Min Heap in linear time

Given an array representing a Max Heap, in-place convert the array into the min heap in linear time.


 

 
The idea is very simple and efficient and inspired from Heap Sort algorithm. The idea is to in-place build the min heap using the array representing max heap. In other words, this is a trick question!! We should not be bothered about whether the given array is max heap or not. The problem is same as building a min-heap from an unsorted array.

 

C++

Download   Run Code

Java

Download   Run Code

Output:

-2 1 5 9 4 6 7

 
The time complexity of above solution is same as building of heap i.e. O(n) and the auxiliary space used by the program is O(1).

 
Exercise: Convert Min Heap to Max Heap in O(n) time

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
arandomguy
Guest

Classic!