Merge 2 Binary Max Heaps

The problem, simply

You get two max heaps, each stored as an array. In a max heap every parent is at least as big as its children. Make one max heap that holds every number from both, and return its array.

For [10, 5, 6, 2] and [12, 7, 9], one correct answer is [12, 10, 9, 2, 5, 7, 6]. Many arrays can be valid max heaps of the same numbers, so any valid one is accepted.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep the first heap and insert every number of the second heap into it, one at a time, with sift up.

1. Copy a into a bigger array.
2. For each number in b, put it at the end and let it climb while it beats its parent.

On the example this gives [12, 10, 9, 2, 5, 6, 7], which is a different but also valid max heap.

class Solution {
    public int[] mergeHeaps(int[] a, int[] b) {
        int[] heap = new int[a.length + b.length];
        System.arraycopy(a, 0, heap, 0, a.length);
        int size = a.length;
        for (int x : b) {
            heap[size] = x;
            int i = size++;
            while (i > 0 && heap[(i - 1) / 2] < heap[i]) {   // climb while bigger than parent
                int p = (i - 1) / 2;
                int t = heap[p]; heap[p] = heap[i]; heap[i] = t;
                i = p;
            }
        }
        return heap;
    }
}

How long it takes: each of the m new numbers may climb log(n + m) rows, so O(m log(n + m)). Extra room: the new array, O(n + m). This is fine when b is tiny, but slow when both heaps are big.

Way 2: the clever way

The heap shape of the inputs does not help much, so throw it away and build fresh. Building a heap from any array is linear time.

1. Glue a and b into one array of size n + m.
2. For every parent, from the last one (size / 2 - 1) back to the root, sift it down: swap with its bigger child while that child is bigger.

class Solution {
    public int[] mergeHeaps(int[] a, int[] b) {
        int size = a.length + b.length;
        int[] heap = new int[size];
        System.arraycopy(a, 0, heap, 0, a.length);          // glue
        System.arraycopy(b, 0, heap, a.length, b.length);
        for (int i = size / 2 - 1; i >= 0; i--) {           // fix from the bottom
            siftDown(heap, size, i);
        }
        return heap;
    }

    private void siftDown(int[] h, int size, int i) {
        int left = 2 * i + 1, right = 2 * i + 2, big = i;
        if (left < size && h[left] > h[big]) big = left;
        if (right < size && h[right] > h[big]) big = right;
        if (big != i) {
            int t = h[i]; h[i] = h[big]; h[big] = t;
            siftDown(h, size, big);
        }
    }
}

How long it takes: bottom up building is O(n + m). Half the nodes are leaves and do nothing, a quarter sink at most one row, and so on, which adds up to less than two swaps per item. Extra room: the merged array, O(n + m).

Watch out for

• Sorting the glued array from big to small also gives a valid max heap, because a sorted array always follows the parent rule. But it costs O((n + m) log(n + m)), so it is not the best.
• Start the build loop at size / 2 - 1 and go down to 0. Going from the root down does not work.
• Handle an empty a or b. System.arraycopy with length 0 is fine.

What interviewers ask next

• Can two heaps be merged faster than O(n + m)? Not with array heaps. Leftist heaps and skew heaps merge in O(log n), and binomial and Fibonacci heaps are built for fast merges.
• Why is build heap O(n) and not O(n log n)? The sum over all nodes of their height is less than n. Only a few nodes are tall.
• How would you merge two min heaps? Same code with every comparison flipped.
• What if you must merge k heaps? Glue all of them and build once, O(total size).

Remember this

Grown-up words: the pyramids are binary max heaps, glueing is concatenation, fixing from the bottom is build heap (heapify), and a kid sliding down to their place is sift down.