Convert Min Heap to Max Heap

Convert an existing min-heap array into a valid max-heap in O(n) using bottom-up heapify.

Convert Min Heap to Max Heap

Problem: Given an array that represents a valid min-heap, convert it in-place into a valid max-heap.

Example:

Input (min-heap): [1, 3, 5, 4, 8, 7]
Output (max-heap): [8, 4, 7, 3, 1, 5] (one valid max-heap)

Note

You don't need to know that the input is a min-heap. Any unsorted array can be turned into a max-heap using the same O(n) bottom-up approach — just run heapify-down with a max comparison starting from n/2 - 1 down to 0.

How to Think About It

Intuition: You don't need to "undo" the min-heap — just forget it's a min-heap at all. Treat the array as unsorted and rebuild it from scratch with max comparisons.

Approach:

Run the exact same bottom-up algorithm as "Build Heap from Array", but use max comparisons in heapify-down (swap with the largest child, not the smallest).
Start at the last non-leaf (n/2 - 1) and work toward index 0. This runs in O(n) for the exact same reason Floyd's algorithm does.

Why Not Just Reverse or Negate?

Reversing a min-heap array does not produce a valid max-heap. The heap structure would be violated.
Negating all values technically works for min-heap libraries (it gives you the effect of a max-heap), but the stored values change.
Rebuilding with max-heapify is the correct, clean in-place approach.

Implementation

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

// Heapify down for max-heap: arr[i] must be ≥ its children
void maxHeapifyDown(vector<int>& arr, int n, int i) {
    while (true) {
        int largest = i;
        int left  = 2 * i + 1;
        int right = 2 * i + 2;
        if (left  < n && arr[left]  > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest == i) break;
        swap(arr[i], arr[largest]);
        i = largest;
    }
}

// Convert any array (including a min-heap) to a max-heap — O(n)
void convertToMaxHeap(vector<int>& arr) {
    int n = arr.size();
    // Start from last non-leaf, run max-heapify down to root
    for (int i = n / 2 - 1; i >= 0; i--)
        maxHeapifyDown(arr, n, i);
}

// arr = {1, 3, 5, 4, 8, 7}  (valid min-heap)
// After convertToMaxHeap: arr = {8, 4, 7, 3, 1, 5}  (valid max-heap)

Walkthrough — `[1, 3, 5, 4, 8, 7]` → Max Heap

Tree view of input (min-heap):
          1
        /   \
       3     5
      / \   /
     4   8 7

Last non-leaf: index 2 (value 5). Children: 7. 7 > 5 → swap
          1
        /   \
       3     7
      / \   /
     4   8 5

Index 1 (value 3). Children: 4, 8. 8 > 3 → swap with 8
          1
        /   \
       8     7
      / \   /
     4   3 5

Index 0 (value 1). Children: 8, 7. 8 > 1 → swap with 8
          8
        /   \
       1     7
      / \   /
     4   3 5

Index 1 (value 1 after swap). Children: 4, 3. 4 > 1 → swap
          8
        /   \
       4     7
      / \   /
     1   3 5

Result: [8, 4, 7, 1, 3, 5] ✓ valid max-heap

Approach	Time	Space
Rebuild with max-heapify (bottom-up)	`O(n)`	`O(1)`
Extract all + re-insert into max-heap	`O(n log n)`	`O(n)`

Convert Min Heap to Max Heap