How to convert min Heap to max Heap in C++

In this tutorial, we will learn how to convert Min Heap to Max Heap in C++. Heaps are one of the most used data structure in many algorithms. Read here for more understanding of Heap sort in C++ array.

Example :

Input :

-2
1           3
9     4    5     7

Output :

9
4              7
1      -2     5       3

C++ program: Convert min Heap to max Heap in C++

At first look, the problem might look complex to be solved in linear time. The approach that we are going to discuss may at first look like an algorithm of O(N log N) time complexity. But it is, in fact, an algorithm with O(N) time complexity. The idea is simple, we just need to build a Max Heap. We start from the rightmost node in the bottommost internal layer and then MaxHeapify all the nodes from bottom to top.

#include<iostream> 
using namespace std; 

void MaxHeapify(int arr[], int i, int n) 
{ 
    int l = 2*i + 1; 
    int r = 2*i + 2; 
    int largest = i; 
    if (l < n && arr[l] > arr[i]) 
        largest = l; 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
        MaxHeapify(arr, largest, n); 
    } 
} 
  
void toMaxHeap(int arr[], int n) 
{ 
    for (int i = (n-2)/2; i >= 0; --i) 
        MaxHeapify(arr, i, n); 
} 
  
void printArray(int* arr, int size) 
{ 
    for (int i = 0; i < size; ++i) 
        cout<<arr[i]<<" ";
} 

int main() 
{ 
    int n;
    cout<<"Enter the number of nodes :";
    cin>>n;
    int minHeap[n], maxHeap[n];
    cout<<"Enter the nodes in Min Heap : ";
    for(int i=0;i<n;i++)
    {
        cin>>minHeap[i];
    }
    toMaxHeap(minHeap, n); 
    memcpy(maxHeap, minHeap, n*sizeof(int));
    cout<<"\nMax Heap array : "; 
    printArray(maxHeap, n); 
    cout<<"\n";
    return 0; 
}

Output :

Enter the number of nodes:7
Min Heap array : -2 1 3 9 4 5 7 
Max Heap array : 9 4 7 1 -2 5 3

 

Comment down below for any doubts.