Merging heaps complexity

Question

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?

Answer 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.