Heap: Convert Min Heap to Max Heap

Problem Statement:

You are given an array representation of Min Heap, convert into Max Heap

Example:

Input: arr[] = [3, 5, 9, 6, 8, 20, 10]

Solution Explanation:

Max Heap:

A Max Heap is a complete binary tree where every parent node is greater than or equal to the children

If a parent is at index i, then left child will be “2*i + 1” and right child will be “2*i + 2”.

Last Non leaf node can be found at (N – 2) / 2

Solution:

We will terate from right to left of the array.
We will start from the last non leaf node, then for each non leaf node perform “heapify” and arrive at the solution.

Time Complexity: O(N)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
using namespace std;

void maxHeapify(vector<int> &arr, int i, int N)
{
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;

    if (left < N && arr[left] > arr[i])
        largest = left;

    if (right < N && arr[right] > arr[largest])
        largest = right;

    if (largest != i) 
    {
        swap(arr[i], arr[largest]);
        maxHeapify(arr, largest, N);
    }
}

void solution(vector<int> &arr)
{
    int n = arr.size();
    for (int i = (n - 2) / 2; i >= 0; --i)
        maxHeapify(arr, i, n);
}


int main()
{
    vector<int> arr = {  3, 5, 9, 6, 8, 20, 10, 12, 18, 9 };

    cout<<"Min Heap : ";
    for (int i = 0; i < arr.size(); ++i)
    cout << arr[i] << " ";

    solution(arr);

    cout<<"\nMax Heap : ";
    for (int i = 0; i < arr.size(); ++i)
    cout << arr[i] << " ";

    return 0;
}

Output

Min Heap : 3 5 9 6 8 20 10 12 18 9 
Max Heap : 20 18 10 12 9 9 3 5 6 8