Max Heap To Min Heap - C++ Solution

1. Introduction

This blog post discusses a crucial problem in heap manipulation: converting a max-heap into a min-heap in-place, in linear time. This problem demonstrates the understanding of heap properties and efficient array transformations.

Problem

Given an array that represents a max-heap, the task is to convert it into a min-heap while maintaining the in-place property of the transformation.

Example:

Input: [9, 4, 7, 1, -2, 6, 5]

Output: [-2, 1, 5, 9, 4, 6, 7]

2. Solution Steps

1. The given array is a max-heap, meaning each parent node is greater than its child nodes.

2. To convert it into a min-heap, we need to ensure each parent node is less than its children.

3. We apply the heapify process starting from the last internal node up to the root node.

4. After heapifying each node, we end up with a min-heap.

3. Code Program

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

// Function to heapify the subtree rooted at index `i`
void minHeapify(vector<int>& heap, int n, int i) {
    int smallest = i; // Initialize smallest as root
    int left = 2 * i + 1; // left child
    int right = 2 * i + 2; // right child

    // If left child is smaller than root
    if (left < n && heap[left] < heap[smallest]) {
        smallest = left;
    }

    // If right child is smaller than smallest so far
    if (right < n && heap[right] < heap[smallest]) {
        smallest = right;
    }

    // If smallest is not root
    if (smallest != i) {
        swap(heap[i], heap[smallest]);
        // Recursively heapify the affected sub-tree
        minHeapify(heap, n, smallest);
    }
}

// Function to convert max heap to min heap
void maxHeapToMinHeap(vector<int>& heap) {
    // Start from the last internal node and go up to the root node
    for (int i = (heap.size() - 2) / 2; i >= 0; i--) {
        minHeapify(heap, heap.size(), i);
    }
}

int main() {
    vector<int> heap = {9, 4, 7, 1, -2, 6, 5};
    maxHeapToMinHeap(heap);

    for (int num : heap) {
        cout << num << " ";
    }
    return 0;
}

Output:

-2 1 5 9 4 6 7

Explanation:

The maxHeapToMinHeap function converts a max-heap into a min-heap. It starts from the last internal node and calls the minHeapify function for each node up to the root. The minHeapify function ensures that for each subtree, the root is smaller than its children, thereby maintaining the min-heap property. After heapifying all nodes, the resulting array represents a valid min-heap.