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 question! It does not matter weather 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.

C++

Download   Run Code

Output:

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

The time complexity of above solution looks like O(nLogn) 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 🙂