Algorithm for merging two max heaps?

Question

Is there an efficient algorithm for merging 2 max-heaps that are stored as arrays?

Answer 1

It depends on what the type of the heap is.

If it's a standard heap where every node has up to two children and which gets filled up that the leaves are on a maximum of two different rows, you cannot get better than O(n) for merge.

Just put the two arrays together and create a new heap out of them which takes O(n).

For better merging performance, you could use another heap variant like a Fibonacci-Heap which can merge in O(1) amortized.

Update: Note that it is worse to insert all elements of the first heap one by one to the second heap or vice versa since an insertion takes O(log(n)). As your comment states, you don't seem to know how the heap is optimally built in the beginning (again for a standard binary heap)

1. Create an array and put in the elements of both heaps in some arbitrary order
2. now start at the lowest level. The lowest level contains trivial max-heaps of size 1 so this level is done
3. move a level up. When the heap condition of one of the "sub-heap"s gets violated, swap the root of the "sub-heap" with it's bigger child. Afterwards, level 2 is done
4. move to level 3. When the heap condition gets violated, process as before. Swap it down with it's bigger child and process recursively until everything matches up to level 3
5. ...
6. when you reach the top, you created a new heap in O(n).

I omit a proof here but you can explain this since you have done most of the heap on the bottom levels where you didn't have to swap much content to re-establish the heap condition. You have operated on much smaller "sub heaps" which is much better than what you would do if you would insert every element into one of the heaps => then, you willoperate every time on the whole heap which takes O(n) every time.

Update 2: A binomial heap allows merging in O(log(n)) and would conform to your O(log(n)^2) requirement.

Answer 2

Two binary heaps of sizes n and k can be merged in O(log n * log k) comparisons. See

Jörg-R. Sack and Thomas Strothotte, An algorithm for merging heaps, Acta Informatica 22 (1985), 172-186.

Answer 3

I think what you're looking for in this case is a Binomial Heap.

A binomial heap is a collection of binomial trees, a member of the merge-able heap family. The worst-case running time for a union (merge) on 2+ binomial heaps with n total items in the heaps is O(lg n).

See http://en.wikipedia.org/wiki/Binomial_heap for more information.