Introduction

Merging two max heaps is simpler than it first sounds because heaps are usually stored as arrays, not pointer-heavy trees. The standard approach is to concatenate both arrays and then rebuild the max heap in linear time using bottom-up heap construction.

Why Concatenate Plus Heapify Is the Standard Solution

A max heap guarantees only one thing locally: every parent is greater than or equal to its children. It does not preserve a fully sorted order. That means you cannot merge two heaps the way you would merge two sorted arrays.

Suppose you have these two heaps stored as arrays:

• heap A: [50, 30, 40, 10, 5, 20]
• heap B: [45, 35, 25, 15, 10]

If you simply append one to the other, the combined array is no longer guaranteed to satisfy the heap property. The fix is to run a build-heap step over the combined array.

This is efficient because building a heap from an arbitrary array takes O(n + m) time, where n and m are the two heap sizes.

The Algorithm Step by Step

The full algorithm is:

1. copy all elements from both heaps into one array
2. run bottom-up max-heap construction on that array
3. return the resulting heap

Here is a complete Python implementation:

1def heapify(arr, n, i):
2    largest = i
3    left = 2 * i + 1
4    right = 2 * i + 2
5
6    if left < n and arr[left] > arr[largest]:
7        largest = left
8
9    if right < n and arr[right] > arr[largest]:
10        largest = right
11
12    if largest != i:
13        arr[i], arr[largest] = arr[largest], arr[i]
14        heapify(arr, n, largest)
15
16
17def build_max_heap(arr):
18    n = len(arr)
19    for i in range(n // 2 - 1, -1, -1):
20        heapify(arr, n, i)
21    return arr
22
23
24def merge_max_heaps(heap1, heap2):
25    merged = heap1 + heap2
26    return build_max_heap(merged)
27
28
29heap1 = [50, 30, 40, 10, 5, 20]
30heap2 = [45, 35, 25, 15, 10]
31print(merge_max_heaps(heap1, heap2))

The exact final array may vary depending on equal values and heapify order, but it will represent a valid max heap.

Why the Running Time Is Linear

At first glance, calling heapify from many positions looks like O(k log k) for k = n + m, but bottom-up heap construction is actually O(k).

The reason is that most nodes are near the leaves, where heapify work is tiny. Only a small number of nodes are near the root, where heapify can travel farther. That weighted cost adds up to linear time.

So the full merge cost is:

• 'O(n + m) to combine the arrays'
• 'O(n + m) to build the heap'
• overall O(n + m)

That is the right target for a practical merge algorithm.

Alternative Strategy: Insert One Heap into the Other

Another possible approach is to take every element from the smaller heap and insert it into the larger heap one by one.

1def sift_up(arr, i):
2    while i > 0:
3        parent = (i - 1) // 2
4        if arr[parent] >= arr[i]:
5            break
6        arr[parent], arr[i] = arr[i], arr[parent]
7        i = parent
8
9
10def insert(heap, value):
11    heap.append(value)
12    sift_up(heap, len(heap) - 1)
13
14
15def merge_by_insertion(heap1, heap2):
16    result = heap1[:]
17    for value in heap2:
18        insert(result, value)
19    return result

This works, but it costs O(m log(n + m)) if you insert m items. That is usually slower than rebuilding the heap from the combined array.

When a Different Heap Type Changes the Answer

If the question were about more specialized heaps such as binomial heaps or Fibonacci heaps, merge complexity would be different because those structures support union operations directly. But for the ordinary binary max heap stored as an array, concatenate plus build-heap is the standard answer.

That distinction matters because many algorithm discussions say "heap" without specifying which heap implementation they mean.

Verifying the Result

After merging, you may want to validate that the resulting array is a legal max heap.

1def is_max_heap(arr):
2    n = len(arr)
3    for i in range(n // 2):
4        left = 2 * i + 1
5        right = 2 * i + 2
6        if left < n and arr[i] < arr[left]:
7            return False
8        if right < n and arr[i] < arr[right]:
9            return False
10    return True
11
12merged = merge_max_heaps(heap1, heap2)
13print(is_max_heap(merged))

That is a useful test when you are implementing heap utilities in an interview practice setting or in a library.

Common Pitfalls

A common mistake is assuming the heaps can be merged like sorted lists. Heaps do not expose elements in sorted order beyond the root property.

Another issue is forgetting to rebuild the heap after concatenation. The combined array remains a complete binary tree layout, but not necessarily a valid heap.

Developers also sometimes overestimate the cost of build-heap and choose repeated insertion instead. For binary heaps, bottom-up heap construction is the better default.

Finally, be clear about the data structure. An answer for binomial heaps or skew heaps does not automatically apply to array-based binary max heaps.

Summary

• For binary max heaps, merge by concatenating the arrays and rebuilding the heap.
• Bottom-up build-heap runs in linear time.
• Repeated insertion also works, but it is usually slower.
• Heaps cannot be merged like sorted arrays because they are only partially ordered.
• Validate the result if you are implementing heap utilities from scratch.