Full and complete answer in order to get credit Thank you Le

Full and complete answer in order to get credit. Thank you

Let H1 and H2 be two (binary) max-heaps with n1 and n2 elements respectively. If every element in H1 is larger than every element in H2, design an algorithm that merges these two heaps into one (binary) max-heap in O(n2) time (assume that both H1 and H2 are large enough to hold n1 + n2 elements).

Solution

Since it is mentioned that H1 each element is larger than H2 elements. So, we need to pick one element from the H2 and place it to the leaf of H1. Since, each element of H1 is greater than that of H2 so there is no need of heapify the heap. Only worst case could be possible that when elements of H2 are added to their own elements and in that case we may need to compare the parent and child and might be swap them. So, algo. will be like this:

1.) For each element in H2, Pick element from H2 and place it as a leaf in H1

2.) Check whether added element is greater than that of parent or not

Hope it helps, do give your response