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 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

Output:

-2 1 5 9 4 6 7

Time complexity of above solution is same as building of heap i.e. O(n).
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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz