Suppose that you have two binary heaps H1 and H2, each with exactly 2k-1 elements. The heaps are represented with explicit binary trees; they are not encoded into arrays. Describe (in precise English, not with code) an O (k) algorithm that will combine H1 and H2 into a single binary heap with 2k 1 - 2 elements.

Question

Computers and Technology

Belinda Hanna

17 February, 00:33

Suppose that you have two binary heaps H1 and H2, each with exactly 2k-1 elements. The heaps are represented with explicit binary trees; they are not encoded into arrays. Describe (in precise English, not with code) an O (k) algorithm that will combine H1 and H2 into a single binary heap with 2k 1 - 2 elements.

+5

Answers (1)

Know the Answer?

Sharon Carey · Answer 1

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)

Create an array and put in the elements of both heaps in some arbitrary order

now start at the lowest level. The lowest level contains trivial max-heaps of size 1 so this level is done

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

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

...

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.