Priority Queues and Heaps

The goal of this lab period is to build a Heap structure that acts as Priority Queue.

---

Tasks

Testing

We've given you a simple tester that you'll use for the checkpoint and that we will use to evaluate your code. But our tester won't help you much with debugging. Write your own tests as you go to help you debug specific methods! It's helpful and we'll check that you have additional tests for your Heap class when grading.

Setup

Make a new folder for this project and copy over your Stack, Queue, and LinkedList classes from the earlier projects (your LinkedList will need to implement both the Stack and the Queue interfaces).

PriorityQueue interface

This week, we'll use this interface for a PriorityQueue. You'll notice that it looks pretty similar to the Queue interface: this is intentional. To some degree, the structures are similar in that a Priority Queue is still a 'type' of Queue: while a Queue typically refers to a FIFO-structure, a Priority-Queue uses a Comparator to make sure that the item polled is the item of greatest priority.

Tasks

1. Create a Heap class

   Create a file Heap.java and create a class with the following declaration: public class Heap<T> implements PriorityQueue<T>.

   This Heap will be an array-based Binary Heap. A binary heap is a rooted-tree structure that follows two rules:

   1. The data of every node in the tree other than the root has value no less than its parent.
   2. The shape of the tree is such that every level other than the last is fully filled and the last is filled from left to right.
   Don't forget that even though a Heap is a binary tree, we are implementing it using an ArrayList which will look very different than what we did for the BST!

2. Create fields for the Heap class

   The Heap will need to maintain the following two fields:

   • A Comparator<T>: this Comparator will help us sort our input. A Comparator has access to a compareTo method that allows us to compare two items of type T to help us organize our structure.
   • An ArrayList that maintains the data in our heap

3. Creating constructors for the Heap class

   Your Heap should support the following constructors:

   • public Heap(Comparator<T> comparator, boolean maxHeap): this Heap should use the given comparator to determine the order of this structure. If maxHeap is true, then a max-heap will be constructed instead (and a new Comparator should be created accordingly). By default, we will make a min heap!
   • public Heap(Comparator<T> comparator): equivalent to Heap(comparator, false).

4. Creating methods for the Heap class

In particular, you must implement the methods of the PriorityQueue interface. In order to do so, I suggest utilizing following private methods:

• private void swap(int idx1, int idx2): swaps the data at idx1 and idx2.
• private int getParentIdx( int idx ): returns the index of the parent.
• private int getLeftChildIdx( int idx ): returns the index of the left child.
• private int getRightChildIdx( int idx ): returns the index of the right child.
• private void bubbleUp( int idx ): when we add a new item to the heap, we'll add it at the leaves of the heap. As such, we'll need to 'bubble' its way up the heap. This (presumably recursive) method checks if idx has a parent and if the item at the parent idx is of lesser priority than idx. If so, we swap the data at idx and parent idx, and recurse on parent idx.
• private void bubbleDown(int idx): when we call poll, we'll need to put a new item into the root. To do so, we'll take whatever item is currently the furthest-right node on the bottom level of the tree and replace the data at the root with that data. Afterwards, we'll need to take that entry and sift it down the heap as long as either of its children has greater priority than it. If a node has lesser priority than both its children, which one should you swap it with (there's a right answer!).

Use the following code for your public String toString() method (it includes the public method and a private, recursive helper):

    public String toString() {
        int depth = 0 ;
        return toString( 0 , depth );
    }
    
    private String toString( int idx , int depth ) {
        if (idx >= this.size() ) {
            return "";
        }
        String left = toString(getLeftChildIdx( idx ) , depth + 1 );
        String right = toString(getRightChildIdx( idx ) , depth + 1 );

        String myself = "\t".repeat(depth) + this.heap.get( idx ) + "\n";
        return right + myself + left;
    }

The remaining methods to implement are just the methods of the PriorityQueue interface.
• public int size(): returns the number of items in the Heap.
• public T peek(): returns the item of highest priority in the Heap. This should be the item stored in the root.
• public void offer(T item): adds the specified item into the Heap. Put item at the next empty spot in the heap, then call bubbleUp.
• public T poll(): returns and removes the item of highest priority. In order to do this, you should take whatever item is in the last spot and replace the root's data with it. Call bubbleDown on the root.
• public void updatePriority(T item): Updates the priority of the given item - that is, ensures that it is 'behind' items with higher priority and 'ahead' of items with lower priority. Assumes all other items' priorities in this Priority Queue have not changed. The main difficulty here is finding the item whose priority you are updating - in this structure as we are currently maintaining it, there can be no expectation of finding the item quickly, so a linear traversal to find the given item is fine.
5. Checkpoint: Does your code pass this simple tester? Note that the tests you have been writing yourself will be more helpful for debugging (and that's why you're writing them!)

---

When you are done, you can proceed to the project.

---