Merge two binary max heaps
Problem
Given two max-heaps stored as arrays, return a single valid max-heap array containing all their elements.
Example 1
Input: a = [10, 5, 6, 2], b = [12, 7, 9] Output: [12, 10, 9, 2, 5, 7, 6] (any valid max-heap)
Also asked as: Merge 2 Binary Max Heaps
Test cases
No automated tests for this problem yet. Use the examples above to check your output.
This problem has no automated tests. Run executes your code and shows what it logs.
View solutionHide solution1 approach
1. Concatenate the arrays and re-heapify
Time O(n + m)Space O(1) extra
A heap is just an array; join both backing arrays and build-heap in O(n).
function mergeMaxHeaps(a, b) { const arr = a.concat(b), n = arr.length; const down = (i) => { for (;;) { let s = i, l = 2 * i + 1, r = 2 * i + 2; if (l < n && arr[l] > arr[s]) s = l; if (r < n && arr[r] > arr[s]) s = r; if (s === i) break; [arr[s], arr[i]] = [arr[i], arr[s]]; i = s; } }; for (let i = (n >> 1) - 1; i >= 0; i--) down(i); return arr;}