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

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

Real tricky indeed!!