Priority Queues

Earlier in the course you saw that a TreeSet can sort the items in a collection and remove duplicates along the way. A PriorityQueue offers a second route to sorted output. Instead of asking a set to keep its items ordered, you place every item into a priority queue and then take the items back out one at a time. The questions this article answers are simple: what order do the items come out in, and what happens to duplicates when you do this?

The technique has two stages. In the first stage, every item is added to the queue. In the second stage, items are removed one at a time inside a loop until the queue is empty. The sorting does not come from the queue handing you a finished list. It comes from the rule that governs each removal, and the rest of this article builds up that rule step by step.

Many learners quietly assume that a priority queue is just an ordinary queue, where the item added first leaves first and the item added last waits its turn. That assumption feels natural because the word queue suggests a line of people. A priority queue follows a different rule. Position in the line does not decide which item comes out. The priority does.

The Java PriorityQueue class is written as a parameterized class, PriorityQueue<T>, which implements a priority queue of objects of type T. The class also implements the Collection<T> interface, so a priority queue object has every method that interface defines. The operations essential to a priority queue, however, are only three: add, remove, and isEmpty.

Before you trace the mechanism, make a prediction. Suppose a collection holds the strings pear, apple, banana, and apple, in that order. The first stage adds all four strings to the queue. The second stage removes them one at a time until the queue is empty. Decide what the printed output will be, paying close attention to whether both copies of apple appear.

The diagram shows the loop as a sequence of remove calls, each followed by the isEmpty check implied by the loop. The second call is where a careless prediction usually fails. A learner who expects each distinct value to appear only once will write apple, banana, pear and stop there. The queue keeps both copies, so the second apple is printed as well.

A remove operation that returns the minimum item only makes sense if the queue can decide, for any two items, which one is smaller. The source compares this to sorting: we need to be able to compare any two items in the queue. Without a way to make that comparison, the queue has no basis for choosing which item comes out next.

Java supports this comparison in two ways. The first is to have the item's class implement the Comparable interface and its compareTo() method. The second is to supply a Comparator to the PriorityQueue constructor. Both ways mirror the two standard approaches to sorting objects, and both give the queue the decision it needs.

The source names String, Integer, and Date as classes that implement Comparable. Objects of these classes can be used directly in a priority queue, which is what makes the sorting technique work without extra setup. The practical rule follows: if the elements you want to sort belong to a class that implements Comparable, you can add them to a PriorityQueue and remove them to get sorted output. The source does not describe how to sort elements of a class that does not implement Comparable, so this article makes no claim about that case.

Consider the same insertion sequence fed into two structures. A plain first-in, first-out queue returns items in the order they were added, so pear, apple, banana comes out as pear, apple, banana. A priority queue given the same insertion sequence returns the minimum-priority item at each step. For strings, that produces lexicographic order, so the output becomes apple, banana, pear.

The two columns in the figure hold the same three values, but the removal order differs. The FIFO column follows arrival order, while the priority queue column follows priority. This difference is the core idea of the whole article: a priority queue is not a line that serves people in turn.

The source presents the PriorityQueue technique as a companion to the TreeSet technique. Both can sort a collection, but they differ on duplicates. A TreeSet removes duplicates as it sorts. The PriorityQueue technique keeps duplicate items in the output. Comparing the two on the same input makes this difference easy to see.

The figure makes the difference concrete. The priority queue holds and outputs four items, including both copies of apple. The TreeSet outputs three, because the duplicate apple is removed. If your goal is a sorted list that preserves every item, the priority queue technique matches that goal. If your goal is a sorted list of distinct values, the TreeSet is the better fit.

The source describes two broad ways to implement a priority queue. The simplest uses a linked list that keeps items in order of increasing priority. In that design, remove is simple, because it removes and returns the first item in the list. Add is the expensive part, because the new item must be inserted into its correct position. The average run time for add in this design is Theta(n), where n is the number of items in the list.

The source also states that priority queues can be implemented so that both add and remove have run time Theta(log(n)), which is much more efficient. That efficient version uses a heap. The source does not explain how a heap arranges its items and says it will not discuss that implementation in the section, so this article does not describe the arrangement. What you can rely on is the complexity contrast between the two designs.

The word heap appears in this topic in a specific sense. A heap is the data structure that an efficient priority queue implementation uses. It is distinct from the other memory the word is often used for, which is the area where objects are created while a program runs. A learner should keep these apart. The heap data structure is an internal technique for keeping a priority queue's ordering efficient. The objects stored in the queue are separate items that the queue refers to.