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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of