#1

Suppose that you have two binary heaps and , each with exactly 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 and into a single binary heap with elements.

Explain why your algorithm is O(k).

#2

Now suppose that and each have exactly elements.

Describe (in precise English, not with code) an O(k) algorithm that will combine and into a single binary heap.

Explain why your algorithm is O(k).

H