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.



Download   Run Code


Download   Run Code


-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

newest oldest most voted
Notify of