Merging Heaps

In this question we consider algorithms for merging two max-heaps. Let n be the number of nodes in max-heap H1 and m be the number of nodes in max-heap H2.

My first attempt is to try to use a divide-and-conquer approach, similar to the algorithm we saw in class for merging two AVL trees. To this end, I want to store the heaps as binary trees (i.e., root node has pointers to left and right child, etc.), instead of using the array implementation as we saw in class.

union(H1, H2):

if H1 == nil: return H2

if H2 == nil: return H1

p = H2.priority

(L, R) = split(H1, p)

L' = union(L, H2.left)

R' = union(R, H2.right)

return new node(L', p, R')

split(H, p):

if H == nil: return (nil, nil)

if p == H.priority: return (H.left, H.right)

if p < H.priority:

(L, R) = split(H.left, p)

R' = new node(R, H.priority, H.right)

return (L, R')

if p > H.priority:

(L, R) = split(H.right, p)

L' = new node(H.left, H.priority, L)

return (L', R)

Question 1: Demonstrate on a specific example that this idea will NOT work.

Question 2: Now that youve convinced me the above was a bad idea, I choose a simple solution: insert every element of H2 into H1. Clearly, this will result in a max-heap. Explain to me why this is not the best idea.

Question 3: Give pseudocode for an algorithm that is linear in n + m. Provide an argument for its correctness and show that it meets the linear running time requirement.