1. Introduction
In this short tutorial, we’ll talk about the Java implementation of the Priority Queue. First, we‘ll see the standard usage and present some examples by ordering the queue in natural and inverse order.
Finally, we’ll see how it’s possible to define a custom order using Java Comparators.
2. The java.util.PriorityQueue
The java.util.PriorityQueue class was provided starting from the JDK 1.5, which also contains other implementations of the AbstractQueue. As we may infer from its name, we use PriorityQueue to maintain a defined ordering in a given collection: the first element (head) of the queue is the most minor element with respect to the ordering we specify. Every retrieval operation of the queue (poll, remove, or peek) reads the head of the queue.
Internally, the PriorityQueue relies on an array of objects. This array is automatically resized if the initial specified capacity (11 by default in JDK 17) is not enough to store all the items. While it’s not mandatory to give an initial capacity to a PriorityQueue, if we already know the size of our collection, it’s possible to avoid automatic resizes, which consume CPU cycles that we’d be better off saving.
In the Javadoc, it’s specified that this implementation takes O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove and add). This can happen thanks to the Balanced Binary Heap data structure that is constantly maintained for every edit to the Queue. It is instead granted linear time for the remove(Object) and contains(Object) methods and constant time for the retrieval methods (peek, element, and size).
3. Natural and Inverse Ordering
In a previous article, we presented how elements inserted into the PriorityQueue are ordered based on their natural ordering. That’s because initializing a priority queue with a null Comparator will directly order elements using the compare operation.
As an example, let’s now see that by providing a standard Integer natural ordering comparator or null, the queue will be ordered in the same way:
PriorityQueue<Integer> integerQueue = new PriorityQueue<>();
PriorityQueue<Integer> integerQueueWithComparator = new PriorityQueue<>((Integer c1, Integer c2) -> Integer.compare(c1, c2));
integerQueueWithComparator.add(3);
integerQueue.add(3);
integerQueueWithComparator.add(2);
integerQueue.add(2);
integerQueueWithComparator.add(1);
integerQueue.add(1);
assertThat(integerQueue.poll())
.isEqualTo(1)
.isEqualTo(integerQueueWithComparator.poll());
assertThat(integerQueue.poll())
.isEqualTo(2)
.isEqualTo(integerQueueWithComparator.poll());
assertThat(integerQueue.poll())
.isEqualTo(3)
.isEqualTo(integerQueueWithComparator.poll());
Let’s now create a PriorityQueue sorted in the inverse natural order. We can achieve this by using the static method java.util.Collections.reverseOrder():
PriorityQueue<Integer> reversedQueue = new PriorityQueue<>(Collections.reverseOrder());
reversedQueue.add(1);
reversedQueue.add(2);
reversedQueue.add(3);
assertThat(reversedQueue.poll()).isEqualTo(3);
assertThat(reversedQueue.poll()).isEqualTo(2);
assertThat(reversedQueue.poll()).isEqualTo(1);
4. Custom Ordering
Let’s now try to define a peculiar ordering for a custom class. First of all, the class should implement the Comparable interface or we should provide a Comparator in the instantiation of the Queue, otherwise, a ClassCastException will be thrown.
For example, let’s create a ColoredNumber class to demonstrate this behavior:
public class ColoredNumber {
private int value;
private String color;
public ColoredNumber(int value, String color) {
this.value = value;
this.color = color;
}
// getters and setters...
}
When we try to use this class in PriorityQueue, it’ll throw an exception:
PriorityQueue<ColoredNumber> queue = new PriorityQueue<>();
queue.add(new ColoredNumber(3,"red"));
queue.add(new ColoredNumber(2, "blue"));
That’s because the PriorityQueue does not know how to order the ColoredNumber object by comparing it to other objects of the same class.
We can provide an ordering by providing a Comparator in the constructor, as we did in the previous examples, or we can implement the Comparable interface:
public final class ColoredNumberComparable implements Comparable<ColoredNumber> {
// ...
@Override
public int compareTo(ColoredNumberComparable o) {
if ((this.color.equals("red") && o.color.equals("red")) ||
(!this.color.equals("red") && !o.color.equals("red"))) {
return Integer.compare(this.value, o.value);
}
else if (this.color.equals("red")) {
return -1;
}
else {
return 1;
}
}
This will grant that every item will be ordered considering the “red” color first and then the value in a natural ordering, meaning that all red-colored objects will be returned first:
PriorityQueue<ColoredNumberComparable> queue = new PriorityQueue<>();
queue.add(new ColoredNumberComparable(10, "red"));
queue.add(new ColoredNumberComparable(20, "red"));
queue.add(new ColoredNumberComparable(1, "blue"));
queue.add(new ColoredNumberComparable(2, "blue"));
ColoredNumberComparable first = queue.poll();
assertThat(first.getColor()).isEqualTo("red");
assertThat(first.getValue()).isEqualTo(10);
queue.poll();
ColoredNumberComparable third = queue.poll();
assertThat(third.getColor()).isEqualTo("blue");
assertThat(third.getValue()).isEqualTo(1);
One final note on multithreading: This Java implementation of the Priority Queue is not synchronized, meaning that multiple threads should not use the same instance of the Java PriorityQueue concurrently.
If more than one thread needs to access a PriorityQueue instance, we should use the thread-safe java.util.concurrent.PriorityBlockingQueue class instead.
5. Conclusion
In this article, we’ve seen how the Java PriorityQueue implementation works. We started with the JDK internals of the class and their performance writing and reading elements. Then, we demonstrated a PriorityQueue with natural ordering and inverse sorting. Finally, we provided a custom Comparable implementation of a user-defined class and verified its ordering behavior.
As always, the code is available over on GitHub.
