实现数据结构中的Heap, 并以此实现Priority Queue.
Learning goals
- Implement a MinHeap
- Understand and analyze the working of Priority Queues
- Write JUnit tests to verify proper implementation
Overview
There are 4 parts to this assignment. All are required before the deadline and should be submitted on Gradescope:
- Part 1: Testing and Implementation of MyMinHeap
- Testing
- Implementation of MyMinHeap
- Coding Style
- Part 2: Autograder Ticket System Simulation using Priority Queue
- Part 3: Conceptual Quiz
- Part 4: Weekly reflection survey (Google Form)
Each part corresponds to its own Canvas “assignment” where your grade on that part will be recorded. More information on submission is given in the Submission Instructions section.
Part 1: Testing and Implementation of MinHeap (individual)
In this part of the assignment, you will implement a MinHeap and write JUnit tests to ensure that your implementation functions correctly.
Read the entire write-up before you start coding.
Download the starter code and put it in a directory in your working environment.
Part 1a - Testing
We provide two test files:
- PublicTester.java
- Contains all the public test cases (visible on Gradescope) we will use to grade your MyMinHeap. (and also, MyPriorityQueue and compareTo in Ticket Class explained in Part 2).
- CustomTester.java
- This file contains 10 generic method headers. You will edit this file. Points will be deducted if test header descriptions are not completed.
Your task: Implement the tests stubbed out in the custom testers. Here are the rules for how you must follow:
- Your tests must test the method they are named for, but they may test any aspect of that method’s behavior that is not already covered by a test in the public tester. Points are awarded only if your test cases pass AND cover cases that the public tester file does not take into account.
- There is no restriction on what error message you use as your string input.
- You MUST NOT copy code from the public tester file.
- DO NOT CHANGE THE TEST METHOD NAMES OR REMOVE ANY OF THE GIVEN 10 METHODS.
- You may add additional test methods, but you are not required to do so.
The table below gives the list of public tests that we will run against your solution. We will also test your code on additional hidden tests. Note that some methods are not tested in the public tester, but will be tested using the hidden tests. You are strongly encouraged to write your own tests to thoroughly test your code, including all edge cases.
| MyMinHeap Test Cases | Public Cases |
|---|---|
| Constructor | Test the MyMinHeap default constructor without any input parameter and MyMinHeap constructor with input data list |
| swap | Test the MyMinHeap swap function on valid indices |
| getParentIdx | Test the MyMinHeap getParentIdx function when the heap is empty |
| getLeftChildIdx | Test the MyMinHeap getLeftChildIdx function when the heap is empty |
| getRightChildIdx | Test the MyMinHeap getRightChildIdx function when the heap is empty |
| getMinChildIdx | Test the MyMinHeap getMinChildIdx function at index 0 |
| percolateUp | Test the MyMinHeap perlocateUp function on a valid index in the middle of the heap |
| percolateDown | Test the MyMinHeap perlocateDown function on a valid index in the middle of the heap |
| deleteIndex | Test the MyMinHeap deleteIndex function at the root of the heap |
| insert | Test the MyMinHeap insert function with a non-null element |
| getMin | Test the MyMinHeap getMin function when the heap is not empty |
| remove | Test the MyMinHeap remove function when the heap is not empty |
| size | Test the MyMinHeap size function when the heap is not empty |
| clear | Test the MyMinHeap clear function when the heap is not empty |
You can find how to compile and run the public tester in the Appendix below.
Part 1b - Implementation of MyMinHeap
Your task: Implement a MinHeap. In the MyMinHeap.java file, add the following:
Instance variables
| Instance Variable | Description |
|---|---|
| public ArrayList | The underlying data structure of MyMinHeap. You must use 0-based indexing to store the heap (the root of the tree at index 0). |
Note: Do not add any other instance variables and do not add any static variables (other than private static final variables to be used as constants).
Constructors
| Constructor | Description |
|---|---|
| public MyMinHeap(); | No-argument constructor that initializes data to an empty ArrayList |
| public MyMinHeap(Collection<? extends E> collection); | Initializes a min-heap using the elements in collection |
Helper Methods
You should find these methods useful to implement the actual functionality of MyMinHeap and also, to implement other helper methods.
Important Note: These helper methods are meant to be called inside the core methods and other helper methods. Thus, the methods that call them should make sure that only valid indices are passed as arguments to the helper methods and/or whether the value returned by these helper methods is within bounds.
Note:
- In practice, these would be private methods, but for our assignment, they will be protected so that we can auto-grade your methods and provide feedback for them. To be clear, these methods are required.
- All tests assume that you use 0-based indexing to store the heap in the array.
| Helper Method Name | Description |
|---|---|
| protected void swap(int from, int to); | Swap the elements at from and to indices in data. |
| protected int getParentIdx(int index); | Calculate and return the parent index of the parameter index. |
| protected int getLeftChildIdx(int index); | Calculate and return the left child index of the parameter index. |
| protected int getRightChildIdx(int index); | Calculate and return the right child index of the parameter index. |
| protected int getMinChildIdx(int index); | Return the index of the smaller child of the element at index. If the two children are equal, return the index of the left child. If the node at index is a leaf (has no children), return -1. |
| protected void percolateUp(int index); | Percolate the element at index up until no heap properties are violated by this element (the heap properties will not be violated once this element’s parent is not greater than it). Do this by swapping the element with its parent as needed. |
| protected void percolateDown(int index); | Percolate the element at index down until no heap properties are violated by this element (the heap properties will not be violated once this element is not greater than its children). If swapping is needed, always swap places with the smaller child. If both children are equal and swapping is needed, swap with the left child. |
| protected E deleteIndex(int index); | Remove the element at index from data and return it. |
Core Methods
| Method Name | Description |
|---|---|
| public void insert(E element); | Add element to the end of the heap (so that it is the right-most element in the bottom-most level) and percolate only the inserted element up until no heap properties are violated (all fixes to the heap properties should be by this percolation) Throw a NullPointerException and do not add to the heap if element is null. |
| public E getMin(); | Return the root (this will be the smallest) element of the heap. If the heap is empty, return null instead. |
| public E remove(); | Remove and return the root (this will be the smallest) element in the heap. Use deleteIndex() helper method here. If the heap is empty return null instead. |
| public int size(); | Return the number of elements in this min-heap. |
| public void clear(); | Clear out the entire heap (the heap should be empty after this call) |
Part 1c - Coding Style
We will grade your code style based on the guidelines posted on Canvas. If you need any clarifications, feel free to ask on Piazza.
All submitted files will be graded for style.
Note: Any tester file(s) will not be graded for magic numbers. In tester file(s), Javadoc tags such as @param or @return are not required, and variable names such as [name]1, [name]2, etc. do not count as non-descriptive. Single character variable names are still considered non-descriptive if not referring to an index.
Part 2 - Autograder Ticket System Simulation using Priority Queue
In this part of the assignment, you will understand how a priority queue can be implemented using a min heap and run a simulation of the Autgrader Ticket System that we use for Tutor hours in this course.
Part 2a - Use MyMinHeap to implement MyPriorityQueue
After completing your MyMinHeap implementation, you can now see how it is used to implement a Priority Queue. You are provided with a MyPriorityQueue.java file that already contains the implementation of a Priority Queue using MyMinHeap.
Your task: Find the TODO comment in the MyPriorityQueue.java file and add a public instance variable called heap of a generic MyMinHeap type. You are strongly encouraged to go through the implementation of the other methods provided to understand how they will be used in Part 2b.
Your MyPriorityQueue will be tested on the 7 test cases provided in PublicTester.java. There are no hidden tests for this.
Note: Do not edit any other part of this file and these tests should pass once you’re done with the TODO!
Part 2b - Use MyPriorityQueue for the Autograder Ticket System Simulator
Ticket.java and Autograder.java together make up the Autograder Ticket System Simulator.
You don’t have to understand how the entire Autograder.java file works. However, you do need to know what the Ticket.java file contains and how you can play around with the priorities of tickets in the queue.
When a student creates a Ticket object, it is added to a Priority Queue in the Autograder class. The order in which the tickets are accepted by tutors is determined by the type of the ticket and the time at which it was first created.
Ticket.java
This class represents a Ticket in the Autograder Ticket System. The Autograder’s MyPriorityQueue contains elements of type Ticket.
Each ticket has a unique ID, name of the student that created the ticket, type of the ticket, status of the ticket in the queue, time at which it was created and time at which it was resolved.
Here are the two instance variables that we will use for this task:
| Instance Variable | Description |
|---|---|
| String ticketType | The type of the ticket. Type can be “Environment setup”, “Debugging”, “Conceptual Doubt”, or “Others” |
| Long createdAt | The time at which the ticket was created |
| Static Variable | Description |
|---|---|
| HashMap | Mapping of different ticketTypes to their corresponding priority ordering. |
For example, the Autograder class creates an orderMap that contains {“Environment SetUp”:1, “Debugging”: 2, “Concept Doubt”: 3, “Others”:4}.|
Your task: Implement the compareTo method in the Ticket class
Your compareTo method will be tested on the 4 test cases provided in the PublicTester.java. There are no hidden tests for this.
| Method | Description |
|---|---|
| public int compareTo(Ticket other) | The order of precedence is the order value of ticketType (can be found from the orderMap) and then, createdAt. |
Now, run the Autograder.java file and observe how the Ticket Queue and Estimated Wait Times change as new tickets are created! There are several questions about this on the Concept Quiz.
Feel free to play around with different priority orderings and observe how the Autograder System behaves. To do this, you can create your own custom orderMap in Autograder.java’s setTicketTypePriority() method.
To compile and run this program call:
javac Autograder.java
java Autograder
Click the "Start" button to start the simulation
Part 3: Conceptual Quiz (individual)
You are required to complete the Conceptual Quiz on Gradescope. There is no time limit on the Quiz but you must submit the Quiz by the PA deadline. You can submit multiple times before the deadline. Your latest submission will be graded.
Part 4: Reflection Survey (individual)
Complete the PA7 reflection. There is an automatic 36-hour grace period for this part.
Submission Instructions
Turning in your code
Submit all of the following files to Gradescope
- MyMinHeap.java
- CustomTester.java
- MyPriorityQueue.java
- Ticket.java
Important: Even if your code does not pass all the tests, you will still be able to submit your homework to receive partial points for the tests that you passed. Make sure your code compiles in order to receive partial credit.