Problem Statement

Given a min-heap in array representation named nums, convert it into a max-heap and return the resulting array.

A min-heap is a complete binary tree where the key at the root is the minimum among all keys present in a binary min-heap and the same property is recursively true for all nodes in the Binary Tree.

A max-heap is a complete binary tree where the key at the root is the maximum among all keys present in a binary max-heap and the same property is recursively true for all nodes in the Binary Tree.

Examples

Example 1:

Input: nums = [10, 20, 30, 21, 23]
Output: [30, 21, 23, 10, 20]

Example 2:

Input: nums = [-5, -4, -3, -2, -1]
Output: [-1, -2, -3, -4, -5]

Different Approaches

1️⃣ Heapify-Down

Intution:

This problem is similar to building heap from a given array. The fact that the given array is a min-heap array can be overlooked, boiling down the problem to building a Max-heap array from the given array.

Approach:

1. Start from the last non-leaf node in the array, as leaf nodes are already min-heaps.
2. Perform a downward heapify operation on each node, ensuring the max-heap property (the parent must be larger than its children) is maintained.
3. The heapify operation compares the current node with its children, swaps it with the larger child if necessary, and recursively heapifies the affected subtree.
4. Once the iterations are over, the given array is converted into a max-heap.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Function to recursively heapify the array downwards
    void heapifyDown(vector<int> &arr, int ind) {
        int n = arr.size(); // Size of the array

        // To store the index of largest element
        int largestInd = ind; 

        // Indices of the left and right children
        int leftChildInd = 2*ind + 1, rightChildInd = 2*ind + 2;
        
        // If the left child holds larger value, update the largest index
        if(leftChildInd < n && arr[leftChildInd] > arr[largestInd]) 
            largestInd = leftChildInd;

        // If the right child holds larger value, update the largest index
        if(rightChildInd < n && arr[rightChildInd] > arr[largestInd]) 
            largestInd = rightChildInd;

        // If the largest element index is updated
        if(largestInd != ind) {
            // Swap the largest element with the current index
            swap(arr[largestInd] , arr[ind]);

            // Recursively heapify the lower subtree
            heapifyDown(arr, largestInd);
        }
        return; 
    }

public:
    // Function to convert a min-heap array to a max-heap array
    vector<int> minToMaxHeap(vector<int> nums) {
        int n = nums.size();
            
        // Iterate backwards on the non-leaf nodes
        for(int i = n/2 - 1; i >= 0; i--) {
            // Heapify each node downwards
            heapifyDown(nums, i);
        }
        
        return nums;
    }
};

// Driver code
int main() {
    vector<int> nums = {10, 20, 30, 21, 23};
    
    cout << "Initial Min-heap Array: ";
    for(int x : nums) cout << x << " ";
    
    // Creating an object of the Solution class
    Solution sol;

    // Function call to convert a min-heap array to a max-heap array
    nums = sol.minToMaxHeap(nums); 
    
    cout << "\nMax-heap converted Array: ";
    for(int x : nums) cout << x << " ";
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) (where N is the number of elements in the array)
  • Each heapify call has a time complexity of O(h), where h is the height of the subtree, h = log(N). The heapify operation is performed for approximately N/2 non-leaf nodes.
  • Due the variable height for all the subtrees, summing the total work done for all the nodes results in an overall time complexity of O(N) for building a heap.
• Space Complexity:O(logN)
  • The recursive calls during heapify require stack space proportional to the height of the heap which will be of the order of log(N) in the worst-case.