Before continuing on, make sure you’re caught up on the lectures through 6/6. Also make sure to pull the starter code.
In this assignment your task is to complete the implementation of a Minimum Binary Heap, a common way we see the Priority Queue ADT realized. You have been given a basic implementation of the PriorityQueue
Interface in SimplePriorityQueue.java
. However, this can be done much more efficiently using a Minimum Binary Heap, and you it is your job to implement the methods in MinimumBinaryHeap.java
.
The PriorityQueue
Interface is the same as the one from class. The methods you need to complete are: 1. enqueue
2. dequeue
3. getMin
Hints and Notes
It is recommended that you use some helper methods to complete this assignment. Some useful ones might be:
isLeaf
: takes an integer index as a parameter, returns false if it hasLeft
getLeft
: takes an integer index as a parameter, returns (index * 2) + 1
getRight
: takes an integer index as a parameter, returns (index * 2) + 2
hasLeft
: takes an integer index as a parameter, checks if getLeft(i)
< size()
hasRight
: takes an integer index as a parameter, checks if getRight(i)
< size()
getParent
: takes an integer index as a parameter, returns (index-1)/2
swap
: takes two indices and swaps the elements at the respective locations
bubbleUp
: bubbles element up to correct location in the heap via comparisons and swaps. Used within enqueue
.
bubbleDown
: bubbles element down to correct location in the heap via comparison and swaps. Used within dequeue
.
Now let us see how much faster the Heap is compared to the List used earlier. In Main
, we have some code set up for you to create the two different types of Priority Queues and fill them with random elements. We fill both with 100,000 elements and time the result of dequeuing 10 times, in nanoseconds. We print the percent decrease when using a Minimum Binary Heap. Feel free to play around here, and also use Main
to test your implmentation.
“Push” your work up to GitHub for backup. By creating “commits”, which you can think of as versioned checkpoints in your workspace, you are not at risk of losing your work. It’s easy to revert back to an old version or to restore your entire workspace on a different computer.
main
branch, and needs to be pushed to your remote backup.USERNAME
with your GitHub username:
https://github.com/comp210-ss1-24/summer210-workspace-USERNAME
All that’s left now is to hand-in your work on Gradescope for grading.
Before doing so, you need to know that before an assignment’s deadline you can resubmit work as many times as you need to without penalty. Portions of assignments are autograded and will provide near-immediate feedback. We want you to resubmit as many times as it takes you in order to earn full autograding credit!
Login to Gradescope and select the assignment named “EX10 Minimum Binary Heap” You’ll see an area to upload a zip file. To produce a zip file for autograding, return back to IntelliJ.
Along the bottom of your window, you should see an option to open a terminal integrated into IntelliJ.
Type the following command (all on a single line):
./submit.sh ex10
In the file explorer pane, look to find the zip file named “ex10_submission.zip”. The script will call it an ex10 submission since that is the package we zipped. If you right click on this file “Open in -> Finder” on Mac, the zip file’s location on your computer will open. Upload this file to Gradescope to submit your work for this exercise.
We are working on rewriting the script to work for Windows! Until then, please navigate to your course workspace in a File Explorer window. Then right click on the src
folder in your exercises directory and compress the directory into a zip folder. You can name it “ex10_submission.zip”
When you upload it to Gradescope, please delete any files that showed up in the src/
folder that were not actually part of ex10
.