Suppose we have p max heaps, with q elements in each. We wish to combine these into a single heap. Each of the following sub-parts describes one approach merging the heaps, and you are asked to derive...

Suppose we have p max heaps, with q elements in each. We wish to combine these into a single heap. Each of the following sub-parts describes one approach merging the heaps, and you are asked to derive the big O running time. MUST show derivation

• 
  We create a new, empty heap H. From each of the input heaps, P, until P is empty we repeatedly remove the highest priority element using the heap delete method, and insert it into H using the heap insert method. What is the worst-case big O running time? Show derivation.
  

• We create a new, empty linked list L. For each of the input heaps, P, we iterate over its internal array and insert each element at the front of L. We then transfer the elements of L into an array, and heapify the array using repeated sift downs. What is the worst-case running time? Show derivation.

• We divide the p input heaps into p/2 pairs, and apply the algorithm from part (b) on each pair, resulting in p/2 heaps. We then repeat this process until we are left with a single heap. What is the worst-case running time? Show derivation.