Example of using PriorityQueue

On the previous page, we introduced Java's PriorityQueue class, which allows you to retrieve elements added to it in sorted order. This means that we can effectively sort some data by adding it to a PriorityQueue and then removing it again. This isn't usually the best way of performing a one-off sort (Collections.sort() on a list will generally perform better), but it will allow us to see how to use a PriorityQueue.

The code is actually very simple. First, we add some random numbers to a PriorityQueue. Note that we initialise the queue specifying approximately how many elements we intend to add, just to help performance. But the queue will grow as we add more:

PriorityQueue q = new PriorityQueue(1000);
Random r = new Random();
for (int i = 0; i < 100; i++) {
  int number = r.nextInt(1000);
  q.add(number);
}

At this point, the items are effectively sorted. It just remains for us to retrieve them. Calling the queue's remove() method will each time retrieve the smallest item still on the queue. So we just keep calling remove() until the queue is empty:

StringBuilder sb = new StringBuilder(5000);
while (!q.isEmpty()) {
  int number = q.remove();
  sb.append(number).append(' ');
}
System.out.println(sb);

Specifying a comparator

PriorityQueue is able to sort/prioritise our integers because the Integer class "naturally sortable"— i.e. it implements the Comparable interface. The same is true of other number classes and strings. For arbitrary objects of our creation, we have two options to make them sortable, as is usual in Java:

• we can make our class implements Comparable;
• we can specify a Comparator when we construct the queue.

A useful comparator that is available "out of the box" is that returned by Collections.reverseOrder(). For example, to sort our integers in descending order, we keep the code above the same, but construct our PriorityQueue with the latter comparator:

PriorityQueue q = new PriorityQueue(1000, Collections.reverseOrder());

Heapsort

We said in our introduction to PriorityQueue that the data structure it uses is a heap. This means that in adding and then removing all our elements, we have effectively performed a type of sort called a heapsort. The heapsort was once a fairly popular algorithm. It has the advantage of being an efficient sort that works in situ— i.e. it doesn't need to make a copy of the data in order to sort. But it has the disadvantage, unlike algorithms such as the mergesort used by Arrays.sort(), of having to "skip about all over memory" as it sorts (or in other words, it has poor memory locality), which is usually not optimal with current memory architectures.