Assignment 5 Implementing a heap Solution

Preamble




A5 involves implementing a heap —either a min-heap or a max-heap— with the added functionality of being able




to change a priority. You will see an example of a common phenomenon: When functionality is added, a data struc-ture has to be changed or a new one added to keep it all efficient.




The result of this assignment is used in A7, which is an implementation of Dijkstra’s algorithm to find a shortest path in a graph. Google maps and other map apps use the shortest path algorithm to find the best route from one place to another.

Keep track of how much time you spent on A5; we will ask for it upon submission.




Last semester, a similar assignment took a mean and median of 4.2 and 4.0 hours. Do it right, and you can get by with writing less than 60 lines of code, in 8 small methods. We suggest getting A5 done well before the due date.




So that A5 doesn’t take too long, we give you a complete JUnit testing class. If your code passes its test cases, your code is correct. You may still lose many points for not adhering to the execution-time bounds given in the specifica-tions of the methods. For example, if an operation should be done in expected constant time and your code searches an array in linear fashion, that will cost points.




Collaboration policy and academic integrity




You may do this assignment with one other person. Both members of the group should get on the CMS and do what is required to form a group well before the assignment due date. Both must do something to form the group: one proposes, the other accepts.

People in a group must work together. It is against the rules for one person to do some programming on this assign-ment without the other person sitting nearby and helping. Take turns "driving" —using the keyboard and mouse.




With the exception of your CMS-registered group partner, you may not look at anyone else's code, from this se-mester or earlier ones, in any form, or show your code to anyone else (except the course staff), in any form.




Getting help




If you don't know where to start, if you don't understand testing, if you are lost, etc., please SEE SOMEONE IM-MEDIATELY —an instructor, a TA, a consultant. Do not wait. A little in-person help can do wonders. See the course homepage for contact information.




The release code




The zip file release.zip contains an Eclipse project with two .java files:




File Heap.java. The methods you must write are marked with //TODO comments, giving the order in which method bodies should be written and tested and giving information on testing. Complete other stubbed-in meth-ods only if you use them.



File HeapTest.java, which has methods to completely test the methods you write.



These files go in the default package. Start a new project, called perhaps a5, and copy the two files into the src direc-tory. You may have to get JUnit5 on the build path. See the Piazza note Assignment A5 for details.




What to do for this assignment




Your job is to implement the methods in class Heap that are marked “//TODO”. These are: add, ensureSpace, swap, bubbleUp, peek, bubbleDown, poll, and updatePriority.

CS2110 Assignment A5 Heaps Due Date: See the CMS 2!







Hints, guidelines, suggestions, requirements




You are responsible for any notes placed on pinned Piazza post Assignment A5! Look at it right way and regular-ly in the next week.
You must implement the methods marked with “//TODO” so that they have the specified time bounds.



Do not remove the “//TODO” comments!



Method upperChild is stubbed in and does not have a “//TODO” note. You do not have to write it, and if you do, you can change its specification. We will not test it by itself. We placed it there because we found it useful.
You can add other methods if you want. Points may be deducted if methods you add do not have good javadoc specifications.



Points will be deducted if you violate the text given in the bodies of the “//TODO” methods.



Do not remove assert statements that we have placed in some methods.



Class HeapTest does all necessary testing. If running HeapTest does not show an error, your class Heap should be correct.



We have declared fields in Heap and written a class invariant for Heap. Study the class invariant. Do not declare any other fields.



Point 12 below discusses the reason for the HashMap.



Using an array for the heap. Generally, one uses an ArrayList for the heap. Instead, we use an array, for two reasons: (1) you get to see how ArrayList can change the size of its backing array when the backing array is too small. For this purpose, you will write procedure ensureSpace. (2) The use of array notation will make the code a lot easier to read.



Min-heap or max-heap? A heap can be a min-heap (e.g. the value with the smallest priority is in the root) or a max-heap (e.g. the value with the largest priority is in the root). The new-expression create one or the other. So, when bubbling up or down, one has to know which one it is, and this can complicate your code.



We have made this easy for you by providing two compareTo functions. Please read the item about this in the pinned Piazza note Assignment A5.




Special problem. Class Heap would be easy to write, using just array d for the heap, except for one issue. A call updatePriority(v, p) changes the priority of value v to p. This requires finding value v in array d, and without any other data structure to help, this could cost time linear in the size of the heap. Not good!



To overcome this problem, we add a field map, of type HashMap<V, Integer, which maps a value in the heap to its index in array d. Please read the item about the class invariant in the pinned Piazza note Assign-ment A5.




What to submit




Remove all your println statements from class Heap; 3 points will be deducted if your code outputs anything.



In the comment at the top, put the hours hh and minutes mm that you spent on this assignment. Be careful chang-



ing hh and mm; don’t change anything else. Doing this carefully helps us not waste time when running a program to extract the times. Put your name(s), netid(s) in, too, and write a few lines about what you thought about this assign-ment.




3. Submit (only) file Heap.java on the CMS.