## Heaps and The Master Theorem

# Heaps and *The Master Theorem*

Copyright © 2015 Bart Massey

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**(*a*,*H*)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?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)*.