Given 2 max heaps
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
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?
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
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.