Convert Min Heap to Max Heap
Description
You are given an array arr of N integers that represents a min heap. Your task is to convert this min heap into a max heap in-place.
A min heap is a complete binary tree where every parent node has a value less than or equal to the values of its children. The smallest element sits at the root.
A max heap is a complete binary tree where every parent node has a value greater than or equal to the values of its children. The largest element sits at the root.
Both heaps are stored as arrays. For a node at index i:
- Its left child is at index
2*i + 1 - Its right child is at index
2*i + 2 - Its parent is at index
(i - 1) / 2
You need to rearrange the elements of the array so that it satisfies the max heap property. You must modify the original array itself — do not return a new array.
Examples
Example 1
Input: N = 4, arr = [1, 2, 3, 4]
Output: [4, 2, 3, 1]
Explanation: The input array represents this min heap:
1
/ \
2 3
/
4
After conversion, one valid max heap is:
4
/ \
2 3
/
1
Here, every parent (4, 2, 3) is greater than or equal to its children. The root holds the maximum element 4.
Example 2
Input: N = 5, arr = [3, 4, 8, 11, 13]
Output: [13, 11, 8, 3, 4]
Explanation: The input min heap:
3
/ \
4 8
/ \
11 13
After conversion to max heap:
13
/ \
11 8
/ \
3 4
Every parent is now greater than or equal to its children. The largest element 13 sits at the root.
Example 3
Input: N = 10, arr = [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]
Output: [20, 18, 10, 12, 9, 9, 3, 5, 6, 8]
Explanation: The given min heap has 10 elements arranged across 4 levels. After applying the conversion algorithm, the largest element 20 moves to the root and the max heap property holds at every level.
Constraints
- 1 ≤ N ≤ 10^5
- 1 ≤ arr[i] ≤ 10^9
- The input array is guaranteed to represent a valid min heap
Editorial
Brute Force
Intuition
The simplest way to think about this problem is to forget that the input has any heap structure at all. If someone hands you a random collection of numbers and asks you to arrange them into a max heap, the most straightforward thing you could do is:
- Sort the numbers in descending order.
- Then build a max heap from that sorted array by inserting elements one by one.
However, an even simpler brute force is: just treat the array as an unordered collection and insert each element into a fresh max heap one at a time. Each insertion into a max heap takes O(log N) time because the element might need to bubble up from a leaf to the root. After inserting all N elements, you have a valid max heap.
Think of it like emptying a box of numbered balls onto a table and then placing them one by one into a priority queue. Each time you add a ball, the queue adjusts itself so the biggest ball is always on top.
Step-by-Step Explanation
Let's trace through with arr = [3, 4, 8, 11, 13]:
Step 1: Create an empty max heap.
- maxHeap = []
Step 2: Insert 3 into the max heap.
- maxHeap = [3]
- Only one element, so the heap property holds trivially.
Step 3: Insert 4 into the max heap.
- Place 4 at the end: [3, 4]
- Compare 4 with parent 3. Since 4 > 3, swap them.
- maxHeap = [4, 3]
Step 4: Insert 8 into the max heap.
- Place 8 at the end: [4, 3, 8]
- Compare 8 with parent 4. Since 8 > 4, swap them.
- maxHeap = [8, 3, 4]
Step 5: Insert 11 into the max heap.
- Place 11 at the end: [8, 3, 4, 11]
- Compare 11 with parent 3 (index 1). Since 11 > 3, swap: [8, 11, 4, 3]
- Compare 11 with parent 8 (index 0). Since 11 > 8, swap: [11, 8, 4, 3]
- maxHeap = [11, 8, 4, 3]
Step 6: Insert 13 into the max heap.
- Place 13 at the end: [11, 8, 4, 3, 13]
- Compare 13 with parent 8 (index 1). Since 13 > 8, swap: [11, 13, 4, 3, 8]
- Compare 13 with parent 11 (index 0). Since 13 > 11, swap: [13, 11, 4, 3, 8]
- maxHeap = [13, 11, 4, 3, 8]
Step 7: Copy the max heap back to the original array.
- arr = [13, 11, 4, 3, 8]
- This is a valid max heap: 13 ≥ 11, 13 ≥ 4, 11 ≥ 3, 11 ≥ 8.
Brute Force — Inserting Elements into a New Max Heap — Watch each element from the original min heap array get inserted into a new max heap, bubbling up to maintain the max heap property after each insertion.
Algorithm
- Create a new empty max heap (or auxiliary array).
- For each element in the input min heap array:
a. Insert the element at the end of the max heap.
b. Bubble up (sift up): while the newly inserted element is greater than its parent, swap it with its parent. - Copy the max heap array back into the original array.
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void siftUp(vector<int>& heap, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (heap[idx] > heap[parent]) {
swap(heap[idx], heap[parent]);
idx = parent;
} else {
break;
}
}
}
void convertMinToMaxHeap(int N, vector<int>& arr) {
vector<int> maxHeap;
for (int i = 0; i < N; i++) {
maxHeap.push_back(arr[i]);
siftUp(maxHeap, maxHeap.size() - 1);
}
for (int i = 0; i < N; i++) {
arr[i] = maxHeap[i];
}
}
};class Solution:
def sift_up(self, heap, idx):
while idx > 0:
parent = (idx - 1) // 2
if heap[idx] > heap[parent]:
heap[idx], heap[parent] = heap[parent], heap[idx]
idx = parent
else:
break
def convertMinToMaxHeap(self, N, arr):
max_heap = []
for val in arr:
max_heap.append(val)
self.sift_up(max_heap, len(max_heap) - 1)
for i in range(N):
arr[i] = max_heap[i]class Solution {
void siftUp(int[] heap, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (heap[idx] > heap[parent]) {
int temp = heap[idx];
heap[idx] = heap[parent];
heap[parent] = temp;
idx = parent;
} else {
break;
}
}
}
void convertMinToMaxHeap(int N, int[] arr) {
int[] maxHeap = new int[N];
for (int i = 0; i < N; i++) {
maxHeap[i] = arr[i];
siftUp(maxHeap, i);
}
for (int i = 0; i < N; i++) {
arr[i] = maxHeap[i];
}
}
}Complexity Analysis
Time Complexity: O(N log N)
We insert N elements into the max heap. Each insertion requires a sift-up operation that may traverse from a leaf to the root. The height of a heap with k elements is O(log k). Summing across all insertions: log(1) + log(2) + ... + log(N) = log(N!) = O(N log N).
Space Complexity: O(N)
We create a separate max heap array of size N to build the heap. This could be avoided by doing the insertions in-place, but the approach fundamentally uses O(N) auxiliary space in this version.
Why This Approach Is Not Efficient
The brute force approach takes O(N log N) time because each of the N insertions may require a sift-up traversal of O(log N) height. While this is a decent time complexity, it is not optimal for this specific problem.
The key inefficiency is that we are treating every element individually, inserting them one by one and sifting each one up from the bottom. We are ignoring a powerful mathematical fact about heaps: leaf nodes already satisfy the heap property trivially because they have no children.
In a complete binary tree with N nodes, approximately N/2 nodes are leaves. That means half the array already satisfies the max heap property without any work! The brute force wastes effort by sifting up each of these leaf elements.
Additionally, we use O(N) extra space for the auxiliary max heap array, which is unnecessary since the conversion can be done in-place.
The insight for a better approach: instead of building a heap from scratch via insertions (top-down), we can rearrange the existing array in-place using a bottom-up heapify strategy that only processes internal nodes — and achieves O(N) time.
Optimal Approach - Bottom-Up Heapify
Intuition
Instead of building a max heap from scratch, we can convert the existing array directly into a max heap using a clever technique called bottom-up heapification (also known as Floyd's heap construction algorithm).
The core insight is elegant: in any complete binary tree stored as an array, the leaf nodes (the second half of the array) already satisfy the max heap property because they have no children to violate it. A node with no children is trivially a valid max heap of size 1.
So we only need to fix the internal nodes — the first half of the array. We process them from the bottom-most internal node up to the root. For each internal node, we perform a max-heapify operation: compare the node with its children, swap it with the larger child if needed, and continue sifting down until the subtree rooted at that node becomes a valid max heap.
Think of it like renovating a building floor by floor, starting from the bottom. Once the lower floors are fixed, they provide a solid foundation. When you fix a higher floor, the floors below it are already correct, so the fix propagates cleanly downward.
The last non-leaf node in an array of N elements is at index (N/2) - 1. We iterate backward from that index down to 0, calling max-heapify at each position.
Remarkably, this bottom-up construction runs in O(N) time — not O(N log N) — because most nodes are near the bottom of the tree and only need to sift down a short distance. The mathematical proof uses the fact that there are N/2 leaves (0 sift-down), N/4 nodes at height 1 (at most 1 swap), N/8 at height 2, and so on. The sum converges to O(N).
Step-by-Step Explanation
Let's trace through with arr = [3, 4, 8, 11, 13] (N = 5):
The tree looks like:
3 (index 0)
/ \
4 8 (index 1, 2)
/ \
11 13 (index 3, 4)
Last non-leaf node = (5/2) - 1 = index 1.
We process indices from 1 down to 0.
Step 1: Identify internal nodes.
- Leaf nodes: indices 2, 3, 4 (values 8, 11, 13) — these are already valid max heaps of size 1.
- Internal nodes: indices 0, 1 (values 3, 4) — these need to be fixed.
- Processing order: index 1 first, then index 0.
Step 2: Max-heapify at index 1 (value 4).
- Left child: index 3, value 11.
- Right child: index 4, value 13.
- Largest among {4, 11, 13} is 13 at index 4.
- Since 13 ≠ 4, swap arr[1] and arr[4]: arr becomes [3, 13, 8, 11, 4].
- Now check index 4 (where 4 landed): index 4 is a leaf, so no further sifting needed.
Step 3: Array state after fixing index 1.
- arr = [3, 13, 8, 11, 4]
- The subtree rooted at index 1 is now a valid max heap: 13 ≥ 11 and 13 ≥ 4.
Step 4: Max-heapify at index 0 (value 3).
- Left child: index 1, value 13.
- Right child: index 2, value 8.
- Largest among {3, 13, 8} is 13 at index 1.
- Since 13 ≠ 3, swap arr[0] and arr[1]: arr becomes [13, 3, 8, 11, 4].
Step 5: Continue sifting down at index 1 (where 3 landed).
- Left child: index 3, value 11.
- Right child: index 4, value 4.
- Largest among {3, 11, 4} is 11 at index 3.
- Since 11 ≠ 3, swap arr[1] and arr[3]: arr becomes [13, 11, 8, 3, 4].
Step 6: Continue sifting down at index 3 (where 3 landed).
- Index 3 is a leaf node (no children within bounds). Stop sifting.
Step 7: Final result.
- arr = [13, 11, 8, 3, 4]
- Verify: 13 ≥ 11 ✓, 13 ≥ 8 ✓, 11 ≥ 3 ✓, 11 ≥ 4 ✓
- Valid max heap achieved in-place!
Bottom-Up Heapify — Converting Min Heap to Max Heap In-Place — Watch how we process only the internal nodes from bottom to top, performing max-heapify (sift-down) at each one to convert the min heap into a max heap.
Algorithm
- Compute the index of the last non-leaf node:
lastNonLeaf = (N / 2) - 1. - For each index
ifromlastNonLeafdown to0:
a. CallmaxHeapify(arr, i, N). - The
maxHeapify(arr, i, N)function:
a. Compute left child index:left = 2*i + 1.
b. Compute right child index:right = 2*i + 2.
c. Find the largest amongarr[i],arr[left], andarr[right](check bounds).
d. If the largest is not at indexi, swaparr[i]witharr[largest].
e. Recursively callmaxHeapify(arr, largest, N)to fix the subtree where the old parent value landed.
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void maxHeapify(vector<int>& arr, int i, int N) {
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) {
swap(arr[i], arr[largest]);
maxHeapify(arr, largest, N);
}
}
void convertMinToMaxHeap(int N, vector<int>& arr) {
// Start from the last non-leaf node and
// heapify each node in bottom-up order
for (int i = (N / 2) - 1; i >= 0; i--) {
maxHeapify(arr, i, N);
}
}
};class Solution:
def max_heapify(self, arr, i, N):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < N and arr[left] > arr[largest]:
largest = left
if right < N and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
self.max_heapify(arr, largest, N)
def convertMinToMaxHeap(self, N, arr):
# Start from last non-leaf and heapify
# each internal node bottom-up
for i in range(N // 2 - 1, -1, -1):
self.max_heapify(arr, i, N)class Solution {
void maxHeapify(int[] arr, int i, int N) {
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) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
maxHeapify(arr, largest, N);
}
}
void convertMinToMaxHeap(int N, int[] arr) {
// Start from the last non-leaf node and
// heapify each node in bottom-up order
for (int i = (N / 2) - 1; i >= 0; i--) {
maxHeapify(arr, i, N);
}
}
}Complexity Analysis
Time Complexity: O(N)
This is the non-obvious and beautiful part. Although each individual maxHeapify call can take up to O(log N) in the worst case, the total work across all calls sums to O(N). Here is why:
- At height 0 (leaves): N/2 nodes, 0 work each → 0 total
- At height 1: N/4 nodes, at most 1 swap each → N/4 total
- At height 2: N/8 nodes, at most 2 swaps each → 2N/8 = N/4 total
- At height h: N/2^(h+1) nodes, at most h swaps each → hN/2^(h+1) total
Summing: Σ (h × N / 2^(h+1)) for h = 0 to log(N) = N × Σ (h / 2^(h+1))
The series Σ (h / 2^(h+1)) converges to a constant (approximately 1), so the total is O(N).
Space Complexity: O(log N)
The conversion is done in-place — we do not create any auxiliary array. The only extra space used is the recursion stack for maxHeapify, which can go as deep as the height of the tree = O(log N). If implemented iteratively, this becomes O(1) space.