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 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.

C++

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).

 
Exercise: Convert Min Heap to Max Heap in O(n) 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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
trackback

[…] [Pending] Convert Min Heap to Max Heap – In Linear Time […]

Hedaetul
Guest
Hedaetul

#include
using namespace std;

void maxHeapify(int arr[], int i, int n){
int left = 2*i+1;
int right = 2*i+2;
int largest = i;
if(leftarr[largest]){
largest = left;
}
if(rightarr[largest]){
largest = right;
}
if(largest != i){
swap(arr[i], arr[largest]);
maxHeapify(arr,largest,n);
}
}

void convertMaxHeap(int arr[], int n){
for(int i=n/2-1; i>=0; i–){
maxHeapify(arr,i,n);
}
}

void printArray(int *arr, int n){
for(int i=0; i<n; i++){
cout<<arr[i]<<" ";
}
}

int main()
{
int n;
int arr[1000];
cout<>n;
cout<<"enter the min heap: ";
for(int i=0; i>arr[i];
}
cout<<"min heap array: ";
printArray(arr,n);
cout<<endl;
convertMaxHeap(arr,n);
cout<<"max heap is: ";
printArray(arr,n);
cout<<endl;
}

wpDiscuz