To better learn about how heaps work by implementing a more tree-like heap.
This is a lab assignment that you’ll be handing in on Moodle. You should complete it on Wednesday Oct 27th, but it isn’t due until Friday Oct 29th at 5:00pm Central.
You should work on this with your in-class partner, but you both need to submit separately.
If you finish it outside of class without your partner, note which sections you completed together and which you completed separately in your
Mount the COURSES drive and remember to save everything into STUWORK. If you don’t do this, everything you write will disappear when you log out!!!!
- Create a new folder in your STUWORK called
- Create your
Collaborations.txtdocument in that folder
- Download the starter code and put it into your HeapLab folder
- Open your
HeapLabfolder in VSCode
In this lab, you’ll make a heap that uses Nodes like we’ve seen in other tree data structures. This is not an efficient way of making a heap at all, the goal is just to practice with the concepts of a heap.
a. First you’ll want to get your Node’s
compareTo set up so that you can use it later. You should compare Nodes based on their priority and since the
priority is an
Integer it also supports
compareTo so you can just use that:
b. You’ll also need to set up your
Node constructor by setting the instance variables.
c. Next you’ll need to set up the
parent method of
Heap, which takes a position and returns the
Node at the parent position of
nodes. Refer to the reading for how to calculate what position that will be.
d. Finally implement the
test method by having it put three
Nodes manually into your
ArrayList and setting all the other things up correctly about those
Nodes, such as which is the root and the parent of the second two nodes, assuming a max heap based on priority. Within
test also call
parent to verify those methods are working correctly.
Now you’ll implement the main pieces of your heap.
a. Implement the
swap method so that it swaps the priorities and values of the nodes, but not the nodes themselves. Think of the nodes as the offices, which don’t change, and just the occupants of the office change. This means you won’t have to change the parent settings at all.
b. Update your test method so that it checks that
swap is working.
heapifyUp, which takes a Node, checks if it is a higher priority than its parent, and if so, swaps the node with its parent and then continues to do so recursively until the node isn’t higher priority than its parent or the node is the root.
d. Update your test method so that it checks that
heapifyUp is working.
e. Finally implement
insert, which should call
heapifyUp after some initial work. Remember to implement
insert using the tree structure, not using the
ArrayList like the reading does. You will need to add the new node to the
ArrayList, but should then attach it to your tree structure and use
f. Test that you are able to insert nodes into your heap and that the top value of the heap’s
ArrayList is the highest priority item you’ve inserted.
You might have noticed that our heap implementation is missing a rather large functionality of a heap, which is removing the top item and then fixing the heap. If you have extra time, implement
Compress your files as a zip, and upload that zip to Moodle under the appropriate assignment. Remember that partners need to submit their code separately and you should share the code you wrote in class with your partner.
This activity is not a homework assignment. That means that you’re evaluated on whether you attempted all parts of it, but your work will not be graded for correctness as long as a clear effort has been made. If you aren’t able to complete some parts, great ways to indicate clear effort are to reach out for help before the deadline (note ways you did so in your Collaborations.txt file) and to use comments in the code to indicate things you tried but what went wrong/where you got stuck.