CS 245 – Practice Assignment 09 Fall, 2019
Practice Assignment 9 – Priority Queues (Heaps)
The goal of this assignment is to practice the implementation of the Priority Queue API as implemented
by yet another important data structure, the Binary Heap. For this assignment, the correctness of the data
structures is measured by how well your implementation conforms to the priority queue specification.
We discussed a priority queue in class. Specifically, the priority queue has two functions: one for adding a
value and the other for removing a value. The functions are specified as follows:
● + void add (int): adds an int (or Integer) instance to the priority queue.
● + int remove(): removes the highest priority item — i.e. the lowest number — from the priority
queue. This function should throw an exception if the priority queue is empty.
However, the priority queue is merely an API; it specifies the functions to be performed without describing
how they should be performed or any storage to be used for the implementation. For your implementation
of the priority queue API, you must use an array-based binary heap.
Requirement 1: Get the files you need. You will copy them to your own GitHub repository using the
1. Log into GitHub. If you do not have a GitHub account, create one via github.com > Sign Up.
2. Point your browser to the URL https://classroom.github.com/a/w8lF-qOk.
3. If necessary, authorize GitHub Classroom by selecting the “Authorize github” button.
4. If available, select your name from the list of names available. This will link your GitHub ID.
5. Accept the assignment by selecting the appropriate button.
If successful, your repository should contain one (1) Java files, Practice09Test.java, which contains
the main function.
Requirement 2: Add to the code in order to make it run. Specifically, your implementation must
implement a class called BinaryHeap.java. This implementation must contain at least the add and
remove functions described above. The add function should always succeed, growing the size of the
array if necessary. The remove function should throw an exception if the binary heap is empty. Your
implementation may contain additional functions if you wish.
Your implementation, in BinaryHeap.java, should start with an array of (initial) size 10. The array must
be doubled in size when there is a need for increased storage.
When the implementation is correct, the output will indicate a starting point for the implementation grade.
This assignment also contains a timing test. The expected timing (20ms) has been established based on
volume of data entered, the efficiency of the binary heap and the median wall clock timing on a
contemporary personal computer. Your individual timing may vary, and your final grade is based not on
the timing but on the efficiency of your implementation as reviewed by the grader.
You are required to submit one classes for this assignment: BinaryHeap.java. Use GitHub to check in the
class required to complete the implementation. On Canvas, submit the URL for your GitHub repository.
The assignment generates text (“Starting point for this assignment”) based on tests of the
functions priority queue functions. The score accompanying this text is the starting point for the grade for
the assignment. Your final grade may be adjusted based on additional items including, but not limited to,
code quality and adherence to the above requirements.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:dmxyzl003