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
  5. In particular, you must implement the methods of the PriorityQueue interface. In order to do so, I suggest utilizing following private methods:

    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.

  6. 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.