Dequeuing Items

The remaining operations that we want to be able to perform with a Priority Queue are to peek at and dequeue the item with the highest priority (lowest order).

Implementing the peek Method

In Java, the peek operation that returns the item with the highest priority (lowest order) is done by the method:

public T peek()

Here, we just need to return the item of type T at the root of the heap (i.e., position 1 of the heap ArrayList.

After implementing the peek method, do not forget to create a unit test that verifies that your peek method is working properly.

Implementing the poll Method

In Java, the dequeue operation that removes and returns the item with the highest priority (lowest order) is done by the method:

public T poll()

Since we are using a heap to store the items of our Priority Queue, the poll method is simply the removeMin method for heaps. Recall from lecture that the removeMin operation:

  1. Saves the item at the root of the heap to a variable
  2. Moves the item from the last leaf in the heap to the root (and removes that last leaf to maintain a complete binary tree)
  3. Moves the moved item in Step 2 into its correct position in the heap by calling the percolateDown method on the root index 1 (to maintain the min heap-order property)
  4. Returns the item saved in Step 1 that was the root of the heap and therefore the item with the highest priority (lowest order).

Hint

In Step 3, we only need to swap the last leaf’s item into the root and percolateDown if the heap is not empty after we removed the last leaf (i.e., the last leaf was not already the root).

We also want to make sure that we only remove from the heap if it contains actual items (so that the null value stays in index 0).

Implementing the percolateDown Method

In order for the poll method to work, we also need to implement the method:

private void percolateDown(int index)

that tries to percolate the item at position index down the tree, following the pseudocode from lecture:

  1. Find the positions of the leftChildIndex and rightChildIndexof index.
  2. If the item at position index does not have children, return since there is no more work to do.
  3. If the item at position index does have children, determine the position of its child with the highest priority (lowest order).
  4. Swap the item at position index with its highest priority (lowest order) child, then recurse on the smallest child’s index.

Testing the poll Method

To finish our implementation of MyPriorityQueue<T>, we should write unit tests to verify that our poll method is implemented correctly. 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. Call poll to dequeue the root of the heap
  4. 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 second array from Warmup 1 [Don’t forget to skip the null at the start of the iterator]

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 percolateDown method public so that you can call it within your unit tests (since it does the majority of the work of the poll method).

Since removing the root of the heap is a special case (see the first Hint above), you might want to create a second unit test verifying that poll also works for this edge condition.

Committing Your Progress

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