Merge two binary max heaps

Easy

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.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

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;
}