Task 3

Open the PriorityQueue.java file (in package task3) which contains a modified PriorityQueue interface from Chapter 20. Notice we have renamed the remove method to removeBest and the interface contains two additional operations: worst and removeWorst. So, as you can see, we modified our familiar PriorityQueue ADT to be able to give us the best and/or worst element(s) on demand.

Example: if the priority queue contains integers where the priorities are based on natural ordering of the values, the method best would return the maximum and worst would return the minimum value.

Suggestion: open the PriorityQueueTest.java and study the tests to solidify your understanding of the operations of PriorityQueue as defined in the starter code for this exam.

We are interested in implementing this modified PriorityQueue interface as efficient as we can. The task was put to class, and a student suggested implementing the PriorityQueue using a circular ranked array representation so that the "best" and "worst" elements are at the opposite ends of the array. This strategy will not work (as the student intended) and in fact signals student's misunderstanding of how the Binary heap implementation of Priority Queue (using a ranked array representation) works.

Please (very briefly) explain it to the student why this strategy will not work and what is their misconception. Write your answer in the README.md file.

Next, we ask you to implement the modified PriorityQueue ADT using two regular priority queues. Open the DoublePriorityQueue.java file. Notice there are two fields in this class:

private java.util.PriorityQueue<T> bestHeap;
private java.util.PriorityQueue<T> worstHeap;

As the names suggest, one priority queue is meant to keep the elements so that we can efficiently extract the "best" and the other does the same thing for the "worst".

This implementation requires doubling the space needed for implementing the PriorityQueue ADT but asymptotically speaking, the space complexity is still $O(n)$.

Your task is to complete the implementation of all operations.

Note:

  • You must have two constructors (one default and another that takes a Comparator).
  • You may not use any data structure other than the two fields bestHeap and worstHeap.
  • You must make use of the operations of java.util.PriorityQueue in your implementation. Consult Oracle's documentation on PriorityQueue.

As you implement the operations, run the tests in PriorityQueueTest.java for that operation. Notice we have offered a small suite of tests; in particular there is no test for the case where the non-default constructor is used. You are encouraged (but not required) to add more tests, especially to test the operations when the non-default constructor is used to instantiate a PriorityQueue.

This last point is imperative to our practice and for all questions, but for the pedantic: you must come up with the best implementation that you can (correctness, efficiency, style, good practices, etc).

In the README.md file, describe the running time of your implementation for best, worst, empty, insert, removeBest and removeWorst. You can assume java.util.PriorityQueue is implemented as a Binary Heap (read the docs for more info).

By "describing" the running time, we mean state it (in asymptotic notation) and (very briefly) explain/justify it.