HeapProblem 16 of 18
Convert min heap to max heap
Problem Statement
Given an array representing a Min Heap, convert it to a Max Heap.
Example:
- Input Min Heap:
[1, 2, 3, 6, 7, 8] - Output Max Heap:
[8, 7, 3, 6, 2, 1] - Explanation:
- Min Heap structure:
1 / \ 2 3 / \ / 6 7 8 - Max Heap structure:
8 / \ 7 3 / \ / 6 2 1
- Min Heap structure:
Approach 1: Extract and Rebuild (Brute Force)
Intuition
Extract all elements from min-heap, build a max-heap from scratch.
Algorithm
- Copy all elements from min-heap array
- Build max-heap using standard heapify
java
public class Solution {
private void maxHeapify(int[] arr, int n, int i) {
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, n, largest);
}
}
public void convertMinToMaxHeap(int[] minHeap) {
int n = minHeap.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapify(minHeap, n, i);
}
}
}Complexity Analysis
- Time Complexity: O(n) - Building heap from array is O(n)
- Space Complexity: O(log n) - Recursion stack for heapify
Approach 2: Direct Conversion - Bottom-Up Heapify (Optimal)
Intuition
The min-heap is already a complete binary tree. We just need to rearrange values to satisfy max-heap property. Apply max-heapify from bottom up.
Algorithm
- Start from last non-leaf node (index n/2 - 1)
- Apply max-heapify on each node moving towards root
- This transforms min-heap to max-heap in O(n) time
java
public class Solution {
private void maxHeapify(int[] arr, int n, int i) {
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, n, largest);
}
}
public void convertMinToMaxHeap(int[] arr) {
int n = arr.length;
// Start from last non-leaf node
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapify(arr, n, i);
}
}
}Complexity Analysis
- Time Complexity: O(n) - Building heap from array is linear
- Space Complexity: O(log n) - Recursion stack depth
Approach 3: Iterative Heapify (Space Optimized)
Intuition
Convert recursive heapify to iterative to avoid recursion stack space.
Algorithm
Same as optimal but with iterative max-heapify.
java
public class Solution {
private void maxHeapifyIterative(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;
}
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
i = largest;
}
}
public void convertMinToMaxHeap(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapifyIterative(arr, n, i);
}
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(1) - No recursion stack
Why Building Heap is O(n)?
Mathematical Analysis
For a heap with n nodes:
- Nodes at height h: n / 2^(h+1)
- Work at height h: O(h)
- Total work: Σ (n / 2^(h+1)) * h for h = 0 to log(n)
This sum converges to O(n), not O(n log n).
Complexity Analysis
- Time Complexity: O(n) - Mathematically proven
- Space Complexity: O(1) with iterative heapify
Key Takeaways
- Conversion is simply rebuilding - We ignore the min-heap property and just build max-heap
- Bottom-up heapify is O(n), not O(n log n)
- The key insight: Most nodes are at lower levels with small heights
- Same approach works for max to min - just change comparison
- The tree structure (complete binary tree) is preserved
- Iterative heapify saves O(log n) stack space
- This demonstrates why building heap is efficient compared to n insertions