Due: Monday, April 24, 2017, 11:59 pm

Priority Queues

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.
2. Create a class public class PQHeap<T> that store 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() 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 the heap. You may want to add private methods to handle the reshaping of the heap.
   • public T remove() removes and returns 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.

When you are ready, move on to Project 8.

© 2017 Ying Li. Page last modified: .