The first operation we want to be able to perform with a Priority Queue is to enqueue a new item.
Before we can work with the heap, we need to be able to calculate the parent and children of a given index. Implement three helper methods:
private int parent(int index) that returns the parent position of index (equal to index / 2)private int leftChild(int index) that returns the left child position of index (equal to 2 * index)private int rightChild(int index) that returns the right child position of index (equal to 2 * index + 1)In Java, the enqueue operation is done by the method:
public boolean offer(T item)
Since we are using a heap to store the items of our Priority Queue, the offer method is simply the insert method for heaps. Recall from lecture and our reading that the insert method:
item as a new leaf at the last index of the heap (to maintain a complete binary tree).item into its correct position in the heap by calling the percolateUp method on the last index of the heap (in order to maintain the min heap-order property)true since the item was inserted into the MyPriorityQueue (necessary for Java Collections)Hint
We do not need to do anything to maintain the size of the heap since we are using the ArrayList’s size method in our own size() method.
In order for the insert method to work, we also need to implement the method:
private void percolateUp(int index)
that tries to percolate the item at position index up the tree, following the pseudocode from lecture:
parent of index.0 where we stored the value null, return from the method because we’ve already reached the root.index should come before the item at position parent.parent.ReadMe
Different from our lecture pseudocode: we added a base case in Step 1, instead of comparing the root with the value -∞, since we cannot store -∞ for all types T
Before moving on to the next part of the lab, we should create unit tests to verify our implementation so far and help us find and remove any bugs. As in previous labs, we can create a Java file that will contain our unit tests by right clicking anywhere in the MyPriorityQueue.java file and selecting “Source Action” from the right click menu. Then, select “Generate Tests”. Use the default name proposed by the IDE of MyPriorityQueueTest. Next, it will prompt you with what methods you want to create tests for. Select the offer method for now.
Inside the newly created MyPriorityQueueTest.java file, create a unit test verifying that the offer method works properly. As one strategy, you could:
MyPriorityQueue<Integer> instanceIterator<Integer> from the iterator() method of MyPriorityQueue<T>, then iterate through the items in the heap to make sure they match your first array from Warmup 1 [Don’t forget to skip the null at the start of the iterator]Hint
Instead of implementing our own Comparator<Integer> object, we can instead get one built in to Java using the code:
Comparator<Integer> comparator = Comparator.naturalOrder();
which will compare integers exactly as we would expect from using <,==, and >.
Hint
Remember the Debugger in Visual Studio Code, which will allow you to inspect the values of variables as you debug your unit tests.
You might also want to temporarily make your percolateUp method public so that you can call it within your unit tests (since it does the majority of the work of the offer method).
Once you have debugged the offer method, you should also create unit tests for the size and clear methods implemented in Part 1 of the lab to make sure they are also working properly.
Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.