Convert Max Heap to Min Heap in linear time

Given a 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 trick question!! We should not be bothered about weather the given array is max heap or not.

 
C++ implementation –
 

Download   Run Code

Output:

-2 1 5 9 4 6 7

Time complexity of above solution is same as building of heap i.e. O(n).
Auxiliary space used by the program is O(1).
 

Recommended Read:
Introduction to Priority Queues using Binary Heaps
Min Heap and Max Heap Implementation in C++
Heap Sort (Out-of-place and In-place implementation in C++ and C)

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 🙂