# Heaps and The Master Theorem

1. Consider the problem of extracting more than one best element from a heap at once.

MULTIPLE-ELEMENT HEAP (MEH) EXTRACTION

INSTANCE: A priority heap H of n elements. An extraction count m ≤ n.

SOLUTION: An array containing the best m elements extracted from H, together with the modified H.

There's an obvious "brute-force" algorithm for this.

BRUTE-FORCE MEH

a ← new array of m elements
for i ← 1 .. m
(a[i], H) ← extract-best(H)
return (aH)

1.1. Argue that the worst-case asymptotic running time of BRUTE-FORCE MEH is O(m lg n).

1.2. Optional Extra Credit: Give an algorithm with worst-case asymptotic running time O(m + f(n)) for some tractable f. What is the running time of your algorithm? When would you use it instead of the brute-force algorithm?

2. Note that the asymptotic worst-case running time for Mergesort is given by

T[0] = 1
T[1] = 1
T[n] = T[n/2] + T[n/2] + O(n)

Use the Master Theorem with this recurrence to argue that the running time of Mergesort is in O(n lg n).