Programming

The ExtrinsicMinPQ Interface¶

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—that is, 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.

One last note: this priority queue can only contain unique items. There cannot be two copies of the same item, though it’s possible for two different items to be assigned the same priority value. In this case, you may break ties arbitrarily.

Implementations¶

Naive Implementation¶

For reference, we have provided NaiveMinPQ, a simple and slow implementation of the ExtrinsicMinPQ interface. You can use the naive implementation when writing your own tests, as a reference to compare results against when testing your own implementation.

peekMin, removeMin, contains, and changePriority use Java’s Stream API to do brute force searches over the entire list of items. This takes time proportional to the length of the list, or $\Theta(n)$.

Heap Implementation¶

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. (You may change the value of this constant to match whatever you implement.)

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. java.util.HashMap, TreeMap, ArrayList, etc.) when developing your code.

Remember that the the $\mathcal{O}(\cdot)$ notation only denotes upper bounds. It is possible to implement some methods with better runtimes.

The Invariant Checker¶

In addition to checking correctness, our tests also make sure your priority queue is backed by a proper min heap. At the minimum, it ensures that:

• The items field contains your heap. The first element starts at the index indicated by your START_INDEX field.
• Every node must have a priority less than or equal to that of its children.

The following output demonstrates what the error messages look like if you have accidentally implemented a max heap:

java.lang.AssertionError: [invariant check] Heap invariants broken at:
  - index 1 (is PriorityNode{item=1, priority=3.0}; has children: [PriorityNode{item=2, priority=1.0}, PriorityNode{item=3, priority=2.0}])

You can see that the invariant has been broken at index 1, and in this case, it is because index 1 has a higher priority than its children.

Tips¶

• Iterating over your entire heap takes linear time, so make sure not to do this in any method!
  • Be careful when using ArrayList methods! Double-check the runtime of any methods you use.
• 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. As a reminder, your class may use other existing ADTs and data structures, so consider what ADTs or data structures might be useful in achieving the required asymptotic runtimes.
• You might find the MinPQ class from the algs4 library to be a helpful reference. We don’t recommend copying and pasting code directly into your implementation, though: while it might seem like this will save you time and effort, it will end up being more work than just building everything yourself from scratch.
• 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 the 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.