Chapter 49: The PriorityQueue Class

We are almost done with the Collection classes. You might have seen in the chapter that introduced collections, talked about a Queue and a class named PriorityQueue. In this chapter we are going to take a look at this class.

So, lets get started!!!

PriorityQueue

The last collection class you’ll need to understand for the exam is the PriorityQueue. Unlike basic queue structures that are first-in, first-out by default, a PriorityQueue orders its elements using a user-defined priority. The priority can be as simple as natural ordering (in which, for instance, an entry of 1 would be a higher priority than an entry of 2). In addition, a PriorityQueue can be ordered using a Comparator, which lets you define any ordering you want. Queues have a few methods not found in other collection interfaces: peek(), poll(), and offer().

import java.util.*;
class PriorityQueueExample {
static class PQsort
implements Comparator { // inverse sort
public int compare(Integer one, Integer two) {
return two - one; // unboxing
}
}
public static void main(String[] args) {
int[] intArray = {1,5,3,7,6,9,8 };
PriorityQueue pQueueObj1 = new PriorityQueue();

for(int x : intArray)
pQueueObj1.offer(x);
for(int x : intArray)
System.out.print(pQueueObj1.poll() + " ");
System.out.println("");

PQsort pqs = new PQsort();
PriorityQueue pQueueObj2 =
new PriorityQueue(10,pqs);

for(int x : intArray)
pQueueObj2.offer(x);
System.out.println("size " + pQueueObj2.size());
System.out.println("peek " + pQueueObj2.peek());
System.out.println("size " + pQueueObj2.size());
System.out.println("poll " + pQueueObj2.poll());
System.out.println("size " + pQueueObj2.size());
for(int x : intArray)
System.out.print(pQueueObj2.poll() + " ");
}
}

This code produces something like this:
1 3 5 6 7 8 9
size 7
peek 9
size 7
poll 9
size 6
8 7 6 5 3 1 null

Let’s look at this in detail. The first for loop iterates through the intArray array, and uses the offer() method to add elements to the PriorityQueue named pQueueObj1. The second for loop iterates through pQueueObj1 using the poll() method, which returns the highest priority entry in pQueueObj1 AND removes the entry from the queue. Notice that the elements are returned in priority order (in this case, natural order). Next, we create a Comparator—in this case, a Comparator that orders elements in the opposite of natural order. We use this Comparator to build a second PriorityQueue, pQueueObj2, and we load it with the same array we used earlier. Finally, we check the size of pQueueObj2 before and after calls to peek() and poll(). This confirms that peek() returns the highest priority element in the queue without removing it, and poll() returns the highest priority element, AND removes it from the queue. Finally, we review the remaining elements in the queue.

Previous Chapter: Chapter 48 - Backed Collections

Next Chapter: Methods Overview for Collections