Priority Queues and Heaps

You will submit your heap and priority queue implementations as a checkpoint in 1 week on November 13th! We'll grade them using the supplied tester. Submit them in your project 7 folder.

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

---

Tasks

Testing

As always, as you are coding up this project create testing files for each class you create exercising the public methods implemented in this class.

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. 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 a node-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.
   In class we used arrays to manage our structure; in this lab, we'll use Nodes to organize the structure of our Heap.

2. Create a container class (a Node)

   As in the LinkedList class, we will use Nodes. This time, however, each Node will have 4 fields: three Node fields for the left, right, and parent references and a fourth field ot type T to store the data of the Node.

3. Create fields for the Heap class

   The Heap will need to maintain the following four 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 int for the number of items in the Heap (the size)
   • And two Nodes: specifically the root of the Heap (the minimal item) and the last Node to have been inserted.

4. Creating constructors for the Heap class

   A 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 the comparator is null, the type T will be assumed to be Comparable (and a new Comparator should be created accordingly). If maxHeap is true, then a max-heap will be constructed instead (and a new Comparator should be created accordingly).
   • public Heap(Comparator<T> comparator): equivalent to Heap(comparator, false).
   • public Heap(boolean maxHeap): equivalent to Heap(null, maxHeap).
   • public Heap(): equivalent to Heap(null, false).

5. 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(Node<T> node2, Node<T> node2): swaps the data between these two nodes.
• private void bubbleUp(Node<T> curNode): when we add a new Node in, 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 curNode has a parent and if that parent's data is of lesser priority than curNode's. If so, we swap the data of curNode with its parent and recurse on curNode's parent.
• private void bubbleDown(Node<T> curNode): when we call poll, we'll need to put a new Node in the root. To do so, we'll take whatever Node is currently the furthest-right leaf and replace the data of the root with that node's 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. Consider the following pseudo-code:

  private void bubbleDown(Node<T> curNode){
      if (cur.left == null){
          // then we know curNode has no children, so we can just end
          return;
      } else if (cur.right == null){
          // then we know curNode has exactly one child, just its left
          // so we just need to determine if we need to swap to the left
          if (the data of curNode's left is of greater priority than curNode){
              swap(curNode, curNode.left);
              bubbleDown(curNode.left);
          }
      } else {
          // then we know that curNode has both a left and right child
          // so we first have to determine which child is of greater priority
          // then determine if we have to swap with that child
          if (the left child is of greater priority than the right){
              if (the left child is of greater priotiy than curNode){
                  swap(curNode, curNode.left);
                  bubbleDown(curNode.left);
              }
          } else {
              if (the right child is of greater priority than curNode){
                  swap(curNode, curNode.right);
                  bubbleDown(curNode.right);
              }
          }
      }
  }
  

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. The main difficulty here is trying to find the right place to put the new item in the Heap before calling bubbleUp. The trick is to start from last, then traverse your way to the next location. If the size before the offer call is odd, this is easy (take one step up, make a new Node to the right). Otherwise, it'll be a bit more complicated. I recommend drawing it out and seeing what the pattern is.
• 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 Node and replace the root's data with it. Like the offer method, the main difficulty here is updating the last Node.
• 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 any linear traversal to find the given item is fine. My solution does the standard binary-tree recursive technique.
6. Testing: Since this project is only a week long, we'll include a simple tester you could use.

Cell Class

README: In order to expedite the process of this project, we're including a fully implemented Cell class and CellType enum. However, do take a few minutes to peruse the methods described below and their implementations to make sure you understand the underlying Cell class.

In a return to familiarity, this project will be based around a 2-D Landscape consisting of individual Cells. Each Cell will have an underyling type; specifically, each Cell will either be an

• unobstrocted cell (free cell)
• obstructed cell

1. Declaring the enum CellType

   To implement this we'll create an additional file CellType.java with the following contents:

   public enum CellType {
       FREE, OBSTACLE;
   }

   An enum is something like a restricted class in Java, in that you're declaring a type of object that can only take on specific values. In this case, we're declaring that the enum type can either be free or obstructed.

2. Cell's Fields

   Each Cell should have the following (private) fields:

   • boolean visited for determining whether we've visited this Cell yet
   • Cell prev for determining which Cell we came from to visit this Cell
   • int row, col for determining which row and column this Cell belongs to in the Landscape
   • CellType type for determining which type of Cell this is

3. Cell's Methods

   All of Cell's methods are basically just getter/setters, but they'll become more obviously useful in the Landscape class.

   • public Cell (int row, int col, CellType type) constructor that sets up the row, col, and type as specified; prev should be null and visited should be false.
   • public int getRow() returns the row
   • public int getCol() returns the column
   • public CellType getType() returns the type
   • public boolean visited() returns visited
   • public Cell getPrev() returns prev
   • public void visitFrom(Cell c) sets visited to true and prev to c
   • public void reset() sets visited to false and prev to null

---

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

---