Due: Monday, April 24, 2017, 11:59 pm
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.
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).
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.
When you are ready, move on to Project 8.
© 2017 Ying Li. Page last modified: .