Enqueuing Items

The first operation we want to be able to perform with a Priority Queue is to enqueue a new item.

Calculating Indices

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:

  1. private int parent(int index) that returns the parent position of index (equal to index / 2)
  2. private int leftChild(int index) that returns the left child position of index (equal to 2 * index)
  3. private int rightChild(int index) that returns the right child position of index (equal to 2 * index + 1)

Implementing the percolateUp Method

In order for the offer method to work, we first 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:

  1. Find the position of the parent of index.
    • If the parent is position 0 where we stored the value null, return from the method because weā€™ve already reached the root (our base case).
  2. Check if the item at position index should come before the item at position parent.
    • If so, swap the items at the two positions and recurse on the position parent (our recursive step).
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

Implementing the offer Method

In Java, the offer operation is done by the method:

public boolean offer(T item)

Since we are using a min 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:

  1. Adds item as a new leaf at the last index of the heap (to maintain a complete binary tree).
  2. Moves the 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)
  3. Returns 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.

Testing the offer Method

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:

  1. Create a new MyPriorityQueue<Integer> instance
  2. Enqueue the numbers in order from the first image in Warmup 1
  3. Get the Iterator<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.

Committing Your Progress

Donā€™t forget to frequently save your progress to GitHub using the add/commit/push commands with git.