HeapProblem 7 of 18
Merge 2 Binary Max Heaps
Problem Statement
Given two binary max heaps as arrays, merge them into a single max heap.
Example:
- Input:
- Heap1:
[10, 5, 6, 2] - Heap2:
[12, 7, 9]
- Heap1:
- Output:
[12, 10, 9, 2, 5, 7, 6] - Explanation: The merged array is converted into a valid max heap.
Approach 1: Concatenate and Sort (Brute Force)
Intuition
Combine both arrays and sort in descending order, then build heap.
Algorithm
- Concatenate both heap arrays
- Sort in descending order
- The sorted array is not a valid heap, so build heap from it
java
import java.util.Arrays;
import java.util.Collections;
public class Solution {
private void heapify(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;
heapify(arr, n, largest);
}
}
public int[] mergeHeapsBruteForce(int[] heap1, int[] heap2) {
int n = heap1.length;
int m = heap2.length;
int[] merged = new int[n + m];
// Concatenate
System.arraycopy(heap1, 0, merged, 0, n);
System.arraycopy(heap2, 0, merged, n, m);
// Sort descending
Integer[] boxed = Arrays.stream(merged).boxed().toArray(Integer[]::new);
Arrays.sort(boxed, Collections.reverseOrder());
for (int i = 0; i < merged.length; i++) {
merged[i] = boxed[i];
}
// Build heap
for (int i = merged.length / 2 - 1; i >= 0; i--) {
heapify(merged, merged.length, i);
}
return merged;
}
}Complexity Analysis
- Time Complexity: O((n+m) log(n+m)) - Due to sorting
- Space Complexity: O(n+m) - For merged array
Approach 2: Concatenate and Build Heap (Optimal)
Intuition
Simply concatenate both arrays and build a max heap using bottom-up heapify. Building heap from array is O(n), making this approach optimal.
Algorithm
- Concatenate both heap arrays
- Build max heap using bottom-up heapify (start from last non-leaf node)
java
public class Solution {
private void heapify(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;
heapify(arr, n, largest);
}
}
public int[] mergeHeaps(int[] heap1, int[] heap2) {
int n = heap1.length;
int m = heap2.length;
int[] merged = new int[n + m];
// Concatenate both heaps
System.arraycopy(heap1, 0, merged, 0, n);
System.arraycopy(heap2, 0, merged, n, m);
int size = n + m;
// Build max heap - O(n)
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(merged, size, i);
}
return merged;
}
}Complexity Analysis
- Time Complexity: O(n+m) - Building heap from array is linear
- Space Complexity: O(n+m) - For merged array
Approach 3: Using Priority Queue
Intuition
Use the standard library's priority queue to handle the heap operations.
Algorithm
- Insert all elements from both heaps into a max priority queue
- Extract all elements to form the merged heap array
java
import java.util.PriorityQueue;
import java.util.Collections;
public class Solution {
public int[] mergeHeapsPQ(int[] heap1, int[] heap2) {
// Max heap priority queue
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
// Insert all elements
for (int num : heap1) {
maxPQ.offer(num);
}
for (int num : heap2) {
maxPQ.offer(num);
}
// Extract elements
int[] merged = new int[heap1.length + heap2.length];
int i = 0;
while (!maxPQ.isEmpty()) {
merged[i++] = maxPQ.poll();
}
return merged;
}
}Complexity Analysis
- Time Complexity: O((n+m) log(n+m)) - Each insert/extract is O(log(n+m))
- Space Complexity: O(n+m) - For priority queue
Key Takeaways
- Sorting approach is inefficient - O((n+m) log(n+m))
- Bottom-up heapify after concatenation is optimal - O(n+m)
- Building heap from scratch is better than inserting one by one
- The heap property of original arrays doesn't help much - we need to rebuild anyway
- Bottom-up heapify works because most nodes are at lower levels with small heights
- This is a classic example where building heap is O(n), not O(n log n)
- Same approach works for merging min heaps (just change comparison)