CS 231: Data Structures and Algorithms (Lab Page)

Title image Lab 8
Fall 2016

Priority Queues

The goal of this lab period is to give you an opportunity to implement a priority queue using a heap.

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.
  2. Create a class public class PQHeap<T> that stores the heap, the number of elements in the heap, and a comparator (Comparator<T>). It should implement the following methods:
    • public PQHeap( Comparator<T> comparator) - a constructor that initialized the empty heap, sets the size to zero, and stores the comparator.
    • public int size() - return the number of elements in the heap.
    • public void add(T obj) - add the value to the heap and increment the size. Be sure to use the Comparator to reshape the heap. You may want to add private methods to handle the reshaping of the heap.
    • public T remove() - remove and return the highest priority element from the heap. Be sure to use the Comparator to reshape the heap. You may want to add private methods to handle the reshaping of the heap.
  3. Test your priority queue. An effective method of testing involves adding many elements (in various 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 that 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 lab, go on to the project.