Skip to main content
Lesson 41 - Priority Queues
Lesson MenuPreviousNext
  
The PriorityQueue Interface page 7 of 9

  1. A priority queue contains items ranked according to some relation of order and provides methods to add an item and to remove and return the smallest item. The items in a priority queue do not have to all be different; if several items have the smallest rank, the removal method can remove and return any one of them. In a Java implementation, we assume that the items are Comparable objects.

  2. The Java library packages do not supply an interface specifically for priority queues. The PriorityQueue interface* shown below (PriorityQueue.java) defines four methods: isEmpty, add, removeMin, and peekMin. The methods in this interface are analogous to the ones in the Stack interface and the Queue interface.

    public interface PriorityQueue
    {
      // Returns true if the number of elements in the
      // priority queue is 0; otherwise, returns false
      boolean isEmpty();
      
      // obj has been added to the priority queue;
      // number of elements in the priority queue is increased by 1
      void add(Object obj);
      
      // The smallest item in the priority queue is removed and
      // returned; the number of elements in the priority queue
      // is decreased by 1. Throws an unchecked exception if the
      // priority queue is empty
      Object removeMin();
      
      // The smallest item in the priority queue is returned; the
      // priority queue is unchanged. Throws an unchecked exception
      // if the priority queue is empty
      Object peekMin();
    }
  3. The Java Library does not supply a class that implements a priority queue. A simplistic class that implements a priority queue can be put together very quickly based on an ArrayList or LinkedList (for the full ArrayList implementation of a priority queue see ArrayPriorityQueue.java). However, a more efficient implementation can be developed based on heaps.


  4. *Adapted from the College Board's AP Computer Science AB: Implementation Classes and Interfaces.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.