Heaps

A priority queue is a dynamic data interface that always returns the entry in the queue with the highest priority. The lab this week is to create a priority queue using an array-based heap data structure.

Testing

As always, as you are coding up this project write tests for each class you create exercising the public methods implemented in this class. For the remaining projects (including this one), these tests should follow the structure of the tests given to you earlier this semester and in the lectures given by Naser.

Tasks

The overall goal of this week is to use a priority queue to find the most common words in each year of reddit comments.

The priority queue will use a heap and a comparator. Whenever a value is removed from the priority queue, it should have the highest priority, as determined by the Comparator.

  1. Setup

    Make a new folder for this week's project. You will also want to copy over the MapSet interface, the BSTMap, the Hashmap, KeyValuePairs, and any other supporting java files.

  2. Create a Heap class

    Create a class public class PQHeap<T> that has fields for the heap data, the number of elements in the heap, and a comparatorComparator<T> (you'll need to import java.util.Comparator). Recall that a comparator should return a value > 0 if and only if the first argument is higher priority than the second.

    Unlike the BSTMap or Hashmap, the Heap needs only a single generic type. That type could be a KeyValuePair<String, Integer>. The heap doesn't care what it's storing and doesn't make use of the concept of a key and a value. It just stores stuff, and the comparator provides the ability to compare what it's storing.

    We'll be using an array-based heap. The heap should be instantiated as an Object array and cast to an array of T objects:

    T[] heap = (T[]) new Object[initialSize];.

    While the choice is ultimately up to you, it's definitely easier to ignore the 0th index of the array and start from index 1 for all computation. This is because it will make it much easier to calculate the left/right/parent indices.

    Implement the following methods for the PQHeap class:

    • public PQHeap(Comparator<T> comparator) - a constructor that initializes the empty heap, sets the size to zero, and stores the comparator.
    • public int size() returns the number of elements in the heap.
    • public int capacity() returns the number of items your heap can currently hold
    • It may be useful to create private internal methods parent, left, and right that take in an index and return the appropriate child/parent index. It could also be useful to create a private internal method private void resize(int newSize) that recreates the array with the given newSize. This will be useful in your offer and poll methods.
    • public void offer(T obj) adds the value to the heap and increments the size. If there's no room for the new item to be added, double the size of the array. Be sure to use the Comparator to reshape/reheap the heap. You may want to add private methods to handle the reheap process.
    • public T peek() returns the highest priority element from the heap.
    • public T poll() removes and returns the highest priority element from the heap. If the size would now be below a quarter of the capacity, halve the capacity. Be sure to use the Comparator to reshape/reheap the heap. You may want to add private methods to handle the reheap process.
  3. Comparing KeyValuePairs

    Eventually, we want to store KeyValuePairs in this heap, so that we can pull words out according to how frequently they appear in the reddit files. To do this, we will need a way to compare KeyValuePairs; we've decided to give this class to you.

CHECK-IN

The due-date for this lab is Sunday 11/20.

Once you have completed the PQHeap class, get started on the project.