Heaps and The Master Theorem

Heaps and The Master Theorem

Copyright © 2015 Bart Massey

  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 (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?

  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).