Given 2 max heaps `h1`

and `h2`

, I want to merge them into a single max heap `H`

. I've gone through the related questions, and understand the `O(n)`

way to merge them: simply concatenate the arrays and call `build_max_heap`

again.

However, I've been thinking of this algorithm, and it seems to me that this is `O(logn)`

and correct as well. Could someone please show if its incorrect, or if its complexity boils down to `O(n)`

as well?

**Algorithm**

```
def merge(h1, h2):
# base cases, if one of them is a leaf node.
if h1.right_child is None and h1.left_child is None:
insert(h1, h2) # insert h1 in h2
return h2
if h2.right_child is None and h2.left_child is None:
insert(h2, h1) # insert h2 in h1
return h1
if value(h1) > value(h2):
new = h1
orphan1, orphan2 = h1.left_child, h1.right_child
new.left_child = max(orphan1, orphan2)
new.right_child = merge(min(orphan1, orphan2), h2)
else:
new = h2
orphan1, orphan2 = h2.left_child, h2.right_child
new.left_child = max(orphan1, orphan2)
new.right_child = merge(min(orphan1, orphan2), h1)
return new
```

It seems as if this traverses the whole depth only twice. Is it incorrect?

pythonalgorithmheappriority-queue answered 3 years ago user2357112 #1

If your heaps don't have any balancing requirements, then merging two binary heaps in O(log(n)) is straightforward. The merge procedure is pretty much the same as the procedure for fixing up the heap after you've just deleted the root.

For the usual implementation of binary heaps, where all elements are stored contiguously in an array, the balancing requirements mean your idea doesn't work. It'd leave a bunch of holes in the array.