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 ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
arandomguy
Guest
arandomguy

Classic!