Heap

Learning Goals¹¶

• Integrate multiple ADTs and data structures to solve a problem with complex requirements.

  Due to the specific runtime requirements of this heap implementation, our solution will need to creatively combine different ADTs and data structures to design a better solution.

• Plan the implementation of a data structure and its invariants.

  At a high level, it’s necessary to determine the invariants that a data structure should maintain before and after every method call, and at a low level, it’s useful to determine how these invariants affect the shared functionality that can be extracted into helper methods. In the process, it may also be necessary to consider which of the invariants these helper methods themselves require in order to function correctly.

Getting the Assignment¶

If you are assigned a partner, consider scheduling a time to go over the spec together and discuss how to collaborate on the project. Like previous projects, one person should also add the other person to their repo as a collaborator, so that everyone has access to the source code.

If IntelliJ doesn’t react to the new folder for whatever reason, refresh Gradle manually through the Gradle tool window (on the right by default):

ExtrinsicMinPQ API¶

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.

Naive 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.

Everyone, Meet 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.

Experiments¶

We’ve provided some basic experiments for your heap, much like the ones present in previous projects. Unlike previous projects, however, the experiments do not have an associated write-up; they’re simply a tool for comparing your heap to the naive implementation. If your heap is implemented correctly, you should see for each experiment that the runtimes of your heap methods have better orders of growth than the naive implementation’s.

If you want to test other aspects of your heap, feel free to alter the experiments or add your own.

Submission¶