# Merging heaps complexity

darkryder Source

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