Joining the same size heap

Question

Can someone explain why the following heap merge algorithm is incorrect?

Suppose we have two (max.) Heaps H1 and H2.

To merge them:

create an artificial node mannequin whose key value is negative infinity and place it in the root with H1 and H2 attached as children. Then follow step O (log n), which collapses the root to the final position of the leaf, where it ultimately is deleted. The resulting structure is a combined heap.

I saw statements both on Wikipedia and elsewhere that merging two pieces of the same size is Operation Theta (n), which contradicts what I wrote above.

Answer 1

At a minimum, since heaps are usually implemented (with implicit references to node placement), the part that you seem to almost ignore ("with H1 and H2 attached as children") has linear complexity in itself.

As the heap is usually implemented, you have a linear collection (for example, an array), where each element of N has elements 2N and 2N + 1 as its elements (for example, with array 1, the children of element 1 are elements 2 and 3, and the children element 2 are 4 and 5). Therefore, you need to interleave the elements from two heaps before we move to the starting point for the merge operation.

If you started with explicitly linked binary trees (only after heap style rules, and not, for example, for binary tree searches), then you are right, the merger can be performed with logarithmic complexity - but I doubt this original article intends to refer to such Structure.

Answer 2

If you implement it like a tree, your decision is right. But, as Jerry said, heap-based array merging cannot be done in sublinear time.

Depending on the frequency and size of the merge, I suggest you use a virtual heap. You can implement it as a bunch of heaps (with arrays). After several merges, you can lazily combine several internal heaps into one big heap.