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:

// The Priority Queue Interface.
interface PriorityQueue<V> {

    // Reinitialize
    void clear();

    // Insert a record
    // priority: the priority for the record being inserted.
    // value: the record being inserted.
    void insert(double priority, V value);

    // Remove and return a record.
    // Remove the record with the minimum priority
    V removeMin();

    // Return the record with the minimum priority
    V min();

    // Return the number of records.
    int size();

    // Build a priority queue from a collection of elements
    // priorities: the priorities for the records being inserted.
    // values: the records being inserted.
    void build(double[] priorities, V[] values);
};

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