Convert Min Heap to Max Heap

Heaps Theory and Implementation Medium

The underlying concepts of min-heaps and max-heaps are used prominently in creating priority queues in software development
Priority queues are widely used in several real-world applications, like Dijkstra's algorithm for shortest path in graph problems, in load balancing and interrupt handling in an operating system, and in data compression algorithms like Huffman coding
The conversion between min-heaps and max-heaps could be beneficial in scenarios where the priority order needs to be reversed or dynamically changed in applications

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:

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

Output: [30, 21, 23, 10, 20]

Explanation:

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

Output: [-1, -2, -3, -4, -5]

Explanation:

Input: nums = [2, 6, 3, 100, 120, 4, 5]

Constraints

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
nums represents a min-heap

Hints

"Start from the last non-leaf node ((n//2) - 1). Apply heapify-down for each node in reverse order. Ensure that every parent is greater than its children by swapping if necessary."
"Find the left child at 2*i + 1. Find the right child at 2*i + 2. Swap with the largest child if nums[i] < nums[child]. Recursively heapify down until the heap property is restored."

Company Tags

Activision Blizzard Broadcom Visa Johnson & Johnson Lyft Epic Games Bain & Company Intel Freshworks HCL Technologies Snowflake Splunk Micron Technology Goldman Sachs Rockstar Games Riot Games Electronic Arts Epic Systems Ubisoft Cerner Docker Cloudflare Pinterest Robinhood PayPal Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/98X8cfAJDrx/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Pre-requisite: Build Heap from a given Array

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:

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

Solution:

#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;
}
import java.util.*;

class Solution {
    
    // Function to recursively heapify the array downwards
    private void heapifyDown(int[] arr, int ind) {
        int n = arr.length; // 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;
        int 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
            int temp = arr[largestInd];
            arr[largestInd] = arr[ind];
            arr[ind] = temp;

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

    // Function to convert a min-heap array to a max-heap array
    public int[] minToMaxHeap(int[] nums) {
        int n = nums.length;

        // Iterate backwards on the non-leaf nodes
        for(int i = n/2 - 1; i >= 0; i--) {
            // Heapify each node downwards to ensure max-heap property
            heapifyDown(nums, i);
        }
        return nums;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {10, 20, 30, 21, 23};
        
        System.out.print("Initial Min-heap Array: ");
        for(int x : nums) {
            System.out.print(x + " ");
        }

        // Creating an object of the Solution class
        Solution sol = new Solution();

        /* Function call to convert the given
        array from min-heap to max-heap */
        nums = sol.minToMaxHeap(nums);

        System.out.print("\nMax-heap converted Array: ");
        for(int x : nums) {
            System.out.print(x + " ");
        }
    }
}
class Solution:
    # Function to recursively heapify the array downwards
    def _heapifyDown(self, arr, ind):
        n = len(arr)  # Size of the array

        # To store the index of largest element
        largestInd = ind

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

        # If the right child holds larger value, update the largest index
        if rightChildInd < n and arr[rightChildInd] > arr[largestInd]:
            largestInd = rightChildInd

        # If the largest element index is updated
        if largestInd != ind:
            # Swap the largest element with the current index
            arr[largestInd], arr[ind] = arr[ind], arr[largestInd]

            # Recursively heapify the lower subtree
            self._heapifyDown(arr, largestInd)
        return

    def minToMaxHeap(self, nums):
        n = len(nums)
        
        # Iterate backwards on the non-leaf nodes
        for i in range(n//2 - 1, -1, -1):
            # Heapify each node downwards
            self._heapifyDown(nums, i)
        
        return nums

def main():
    nums = [10, 20, 30, 21, 23]
    
    print("Initial Min-heap Array: ", end="")
    for x in nums:
        print(x, end=" ")

    # Creating an object of the Solution class
    sol = Solution()

    # Function call to convert the given array from min-heap to max-heap
    nums = sol.minToMaxHeap(nums)

    print("\nMax-heap converted Array: ", end="")
    for x in nums:
        print(x, end=" ")

if __name__ == "__main__":
    main()
class Solution {
    // Function to recursively heapify the array downwards
    heapifyDown(arr, ind) {
        let n = arr.length; // Size of the array

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

        // Indices of the left and right children
        let leftChildInd = 2*ind + 1;
        let 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
            [arr[largestInd], arr[ind]] = [arr[ind], arr[largestInd]];

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

    // Function to convert the min-heap array to max-heap array
    minToMaxHeap(nums) {
        let n = nums.length;
        
        // Iterate backwards on the non-leaf nodes
        for(let i = Math.floor(n/2) - 1; i >= 0; i--) {
            // Heapify each node downwards
            this.heapifyDown(nums, i);
        }
        
        return nums;
    }
}

// Driver code
function main() {
    let nums = [10, 20, 30, 21, 23];
    
    process.stdout.write("Initial Min-heap Array: ");
    for(let x of nums) {
        process.stdout.write(x + " ");
    }

    // Creating an object of the Solution class
    let sol = new Solution();

    // Function call to convert the given array from min-heap to max-heap
    nums = sol.minToMaxHeap(nums);

    process.stdout.write("\nMax-heap converted Array: ");
    for(let x of nums) {
        process.stdout.write(x + " ");
    }
}

// Run the driver code
main();

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.

Code

Problem List