Draw the state of the heap from the previous question after a single call to removeMin.

Repeat the previous exercise for two more calls to removeMin.

Here is an interface describing a simple Priority Queue ADT:

/*
 * MinQueue interface. 
 */
public interface MinQueue<P extends Comparable<P>, E> {

  /**
   * Enqueue the provided value with the indicated priority.
   */
  void enqueue(P priority, E item);

  /**
   * Return and remove the item with the lowest associated priority.
   */
  E dequeue();

  /**
   * Return, but do not remove, the item with the lowest associated priority.
   */
  E peek();

  /**
   * Return the number of elements in this MinQueue.
   */
  int size();

  /**
   * Return a MinQueue constructed from the provided priorities and items.
   */
  MinQueue<P, E> buildMinQueue(P[] priorities, E[] items);
}

• Consider four concrete implementations of this ADT:
  1. priority/value pairs are stored in a sorted array.
  2. priority/value pairs are stored in a (non-self balancing) binary search tree.
  3. priority/value pairs are stored in an AVL tree.
  4. priority/value pairs are stored in a Heap. (Note that both 1. and 4. will make use of dynamic arrays.)
• What are the worst-case big-\(\Theta\) running times for the following operations. For “BST” assume the worst-case tree structure.

• Assuming that a single reference requires 8-bytes of space, what is the worst-case space overhead for of the implementations above? Assume that each implementation stores the key value pairs in a Pair class and that we are not counting the space required for the pairs. You may also assume that all tree nodes contain two child references, and that AVL trees require a parent reference.

• Which implementation do you think makes the most sense?