Java Priority Queue (+ Comparator Example)

Learn to create, use and understand how a priority queue works in Java. We will examples of queues with elements stored in natural order as well as custom order using Comparator instance.

// Natual ordered queue
PriorityQueue<Integer> numbers = new PriorityQueue<>();   

// Custom ordered queue
Comparator<Task> nameComparator = Comparator.comparing(Task::name);
PriorityQueue<Integer> numbers = new PriorityQueue<>(nameComparator);

1. Introduction

1.1. What is a PriorityQueue

Java PriorityQueue class is an unbounded Queue interface implementation that processes the queued items based on their priorities. The PriorityQueue is different from other standard queues that implement the FIFO (First-In-First-Out) algorithm.

In PriorityQueue, the added items are retrieved according to their priorities. By default, the priority is determined by the natural ordering of elements. Default priority can be overridden by a Comparator provided at queue construction time.

It is important to note that, when printing the content of the priority queue, the items may not be stored by their priorities. However, items are always retrieved in sorted order.

1.2. PriorityQueue Example

Let us understand how to use a PriorityQueue in application code for adding and removing elements.

PriorityQueue<Integer> numbers = new PriorityQueue<>();

// Add elements with the add() or offer() methods
numbers.offer(1);
numbers.add(3);
numbers.add(2);

System.out.println("PriorityQueue: " + numbers);

// Examine the items without fremoving from queue
System.out.println("Item: " + numbers.peek());  

// Retrieve the items and remobve from queue
System.out.println("Item: " + numbers.poll());
System.out.println("Item: " + numbers.poll());
System.out.println("Item: " + numbers.poll());

The program output:

PriorityQueue: [1, 3, 2]

Item: 1

Item: 1
Item: 2
Item: 3

2. Features of a PriorityQueue

Let’s note down a few important features of the PriorityQueue.

• PriorityQueue is an unbounded queue that grows dynamically.
• The default initial capacity is '11' which can be overridden using initialCapacity parameter in the appropriate constructor.
• It does not allow null.
• By default, the items in the priority queue are ordered in the natural order.
• The queue items must be Comparable to determine their priorities when the Comparator is not used for custom ordering. Doing so may result in ClassCastException
•  The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
• The head of the PriorityQueue is the least element based on the natural ordering or the Comparator based ordering.
• If multiple objects are present of the same priority, then the queue can poll any one of them randomly.
• PriorityQueue is not thread-safe. Use PriorityBlockingQueue in a concurrent environment.
• It provides O(log(n)) time performance for add and poll methods.
• The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need the ordered traversal, consider using Arrays.sort(pq.toArray()).

3. Different Ways to Create a PriorityQueue

Generally, we consider the order of elements in the queue as the deciding factor for creating a priority queue. Based on either natural ordering or custom ordering, priority queue can be created in two ways:

3.1. PriorityQueue with Comparable for Natural Ordering

To create a priority queue, use one of the following constructors:

• PriorityQueue(): creates an instance with the default initial capacity (11) with elements sorted by natural ordering.
• PriorityQueue(capacity): creates an instance with the specified initial capacity with elements sorted by natural ordering.

PriorityQueue<Integer> numbers = new PriorityQueue<>();

For example, we have a record Task that implements the Comparable interface and implements the comparison logic using its priority field.

record Task(long id, String name, int priority) implements Comparable<Task> {

  @Override
  public int compareTo(Task other) {
    return Integer.compare(other.priority, this.priority);
  }
}

When we add a few tasks to the priority queue and retrieve them, we get the tasks based on priority.

PriorityQueue<Task> priorityQueue = new PriorityQueue<>();

priorityQueue.add(new Task(10001, "Task 1", 5));
priorityQueue.add(new Task(10002, "Task 2", 1));
priorityQueue.add(new Task(10003, "Task 3", 10));


while (!priorityQueue.isEmpty()) {
  System.out.println(priorityQueue.poll());
}

The program output:

Task[id=10003, name=Task 3, priority=10]
Task[id=10001, name=Task 1, priority=5]
Task[id=10002, name=Task 2, priority=1]

3.2. PriorityQueue with Comparator for Custom Ordering

If we want to define a custom priority order that is different from the natural ordering of objects, we can use Comparator.

For example, we can define the sorting order of tasks by their task id field as follows:

Comparator<Task> idComparator = Comparator.comparing(Task::id);

We pass the comparator instance to the constructor of PriorityQueue to enforce the new sorting order.

PriorityQueue<Task> priorityQueue = new PriorityQueue<>(idComparator);

priorityQueue.add(new Task(10001, "Task 1", 5));
priorityQueue.add(new Task(10003, "Task 3", 10));
priorityQueue.add(new Task(10002, "Task 2", 1));

while (!priorityQueue.isEmpty()) {
  System.out.println(priorityQueue.poll());
}

The program output confirms that even though the tasks were added with random ids, they are retrieved in the correct order.

Task[id=10001, name=Task 1, priority=5]
Task[id=10002, name=Task 2, priority=1]
Task[id=10003, name=Task 3, priority=10]

4. When to Use a PriorityQueue

Here are some scenarios where using a PriorityQueue can be beneficial:

• Task Scheduling: When scheduling tasks based on their priority, a PriorityQueue can be helpful to determine the next task with the highest priority efficiently.
• A* Search Algorithm: It is a popular pathfinding algorithm used in various applications, such as route planning and game development. PriorityQueue can prioritize nodes based on their total estimated cost from the start to the goal.
• Dijkstra’s Algorithm: It finds the shortest path in a graph from a single source to all other nodes. A PriorityQueue efficiently selects the next node with the shortest distance during the algorithm’s execution.

5. Conclusion

In this Java queue tutorial, we learned to use PriorityQueue class which is able to store elements either by default natural ordering or custom order specified by a Comparator.

Drop me your questions in the comments section.

Happy Learning !!