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

Java

Download   Run Code

Output:

-2 1 5 9 4 6 7

 
The time complexity of above solution is same as building of heap i.e. O(n) and the 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 🙂
 


Get great deals at Amazon




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