CS 231: Lab #9

Title image Spring 2020


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

Video: Heaps


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. The Comparator should work just like the Comparator objects from the past two projects.

  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>. The comparator should return a value > 0 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.

    You can implement a node-based heap or an array-based heap. If you do an array-based heap, use an array of type Object. Both implementation styles need to be able to grow to the size necessary to hold the data. In a node-based heap, you may want each node to have pointers to both its children and its parent. [Hint: the array-based heap is much simpler, so do it first.]

    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 void add(T obj) adds the value to the heap and increments the size. 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 remove() removes and returns the highest priority element from the heap. Be sure to use the Comparator to reshape/reheap the heap. You may want to add private methods to handle the reheap process.
    • If you are creating an array-based heap, it may be useful to create internal methods parent, leftChild, and rightChild that take in an index and return the appropriate child/parent index.
  3. Test your priority queue

    An effective method of testing involves adding many elements (in a variety of orders), and then removing them, checking to see if they are removed in sorted order. You will likely want to add a method that will allow you to print your elements in the order they are stored so you can fix any bugs. Here is a link to a test file that will test it with Integers and then with KeyValuePairs. You will need to put your KeyValuePairs code into your directory if you want this to work.

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