CS 231: Lab #8

Title image Spring 2018

Heaps

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.

Tasks

You will be implementing a priority queue that uses a comparator. Whenever you remove a value from the priortiy queue, it should have the highest priority (as determined by the Comparator).

  1. 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 class public class PQHeap<T> that has fields for the heap, 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.

    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.

    Implement the following methods:

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

  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 Hashmap class, get started on the project.