Combining Heaps

a) Suppose that you have two binary heaps H₁ and H₂, each with exactly 2^k-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 H₁ and H₂ into a single binary heap with 2^k+1- 2 elements.

b) Explain why your algorithm from the previous question is O(k).

c) Now suppose that H₁ and H₂ each have exactly 2^k-2 elements. Describe (in precise English, not with code) an O(k) algorithm that will combine H₁ and H₂ into a single binary heap.

d) Explain why your algorithm from the previous question is O(k).