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

Given an array representing a Min Heap, convert Min Heap into a Max Heap. The conversion should be done inplace and in linear time.


The idea is very simple and efficient and inspired from Heap Sort algorithm. The problem looks complex at first glance but this problem is no different with building a max-heap from an unsorted array. This is a trick problem! It does not matter whether the given array is a min heap or not. We can simply build the max heap from the given array by starting from the last internal mode (rightmost, bottom-most node) of min Heap and heapify all internal modes in bottom-up manner to build the Max heap.


Download   Run Code


Array representation of Max Heap is : 10 6 8 1 3 4 5


Download   Run Code


[-2, 1, 5, 9, 4, 6, 7]

The time complexity of above solution looks like O(nlog(n)) at first look. But the complexity is same as the time complexity of building a heap i.e. O(n).

Exercise: Convert Max Heap to Min Heap in linear 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

Notify of
Sort by:   newest | oldest | most voted

In the text it says “weather”. I bet you meant “whether”