A priority queue is like a queue in that you can enqueue and dequeue elements. However, the element that gets dequeued is the one with the minimum value of a feature, called its priority. We will use a comparator to compare elements and learn which one has the lowest priority. We will use the following interface for the priority queue:
public interface PriorityQueue<E> { E checkMinimum(); E dequeueMinimum(); void enqueue(E value); }
We require the following set of behaviors from the methods:
checkMinimum
: This method must return the next value to be dequeued without dequeuing it. If the queue is empty, it must return null.dequeueMinimum
: This must dequeue the element with the minimum priority and return it. It should return null when the queue is empty.enqueue
: This should insert a new element in the priority queue.
We would also like to do these operations as efficiently as possible. We will see two different ways to implement it.