Programming

ExtrinsicMinPQ¶

The main task for this assignment will be to develop an array-based implementation of the ExtrinsicMinPQ interface. The priority for each item will be extrinsic to the object–rather than relying on some sort of comparison function to decide which item has less priority than another, we manually assign priorities by passing in numbers along with the items.

Reference implementation¶

The starter code includes a working NaiveMinPQ. The implementation is called “naive” because it uses a simple and slow implementation of the ExtrinsicMinPQ interface. peekMin(), removeMin(), contains(), and changePriority() use Java’s Stream API to do brute force searches over the entire list of items resulting in runtimes proportional to the length of the list, or $\Theta(n)$.

ArrayHeapMinPQ¶

An enhanced binary heap priority queue supported by a HashMap that associates each item with its heap index to speed-up various methods. Your ArrayHeapMinPQ must follow each of these invariants:

• Required fields:
  • You must store your min-heap in the field named items. It should be an ArrayList of PriorityNodes, the class used to store items along with their priorities.
  • Your heap ArrayList must start at the index indicated by START_INDEX.
• Required runtimes (where $N$ is the heap size):
  • peekMin(), contains(), size() and changePriority() must run in $\mathcal{O}(\log N)$ time.
  • add() and removeMin() must run in $\mathcal{O}(\log N)$ time except for the rare resize operation.
• You may not import other priority queue implementations. However, you are allowed to import other built-in Java structures (ex. HashMap, TreeMap, ArrayList, etc.) when implementing ArrayHeapMinPQ.

Tips¶

• Iterating over your entire heap takes linear time, so make sure not to do this in any method! Likewise, be careful if you use ArrayList methods to make sure they follow the correct runtimes for our priority queue.
• Sometimes, if some computation is slow and expensive, it’s useful to store some extra information to help speed up that computation at the cost of some extra memory usage.
• We’ve provided some tests in ArrayHeapMinPQTests, but there are essentially no tests for changePriority, nor are there any tests checking that your heap works at larger sizes. It may be helpful to write some tests for changePriority before you start implementing it, since considering the possible test cases can help you plan out your approach.

Grading Details¶

Most of the points for this assignment will be allocated towards evaluating the correctness of ArrayHeapMinPQ, but a few points will be allocated towards efficiency. The stress tests on the grader have 3 sequential sections to test add(), changePriority(), and remove(), respectively (all using the same heap instance). Because the sections run sequentially, there are a few cases that could occur during grading:

• Your code throws an exception. In this case, all subsequent stress tests are skipped, and you get no points from any stress tests.
• Your code takes an excessively long time to run. In this case, the stress tests will throw an exception, and you get the same outcome as above.
• Your code runs, but returns incorrect values in the remove section. In this case, no points will be awarded from the stress tests.
• Your code runs and returns the correct values in the remove section. In this case, the runtimes for each section will be scored independently.

Submission¶

If you’re working in a group, the partner who submits must add the other partner as a group member on Gradescope. Here’s a video demonstrating that process. You’ll also need to re-add group members whenever you resubmit to the same assignment, even if you already did so on a previous submission.