Table of Contents
Overview
A priority queue is an interesting data structure in Java. The key term here is “priority”. That means the queue is ordered by priority of the elements, not the order they are added.
Let’s consider an example:
private static void priorityQueueExample() {
Queue<Integer> priority = new PriorityQueue<>();
priority.add(1);
priority.offer(0);
priority.add(4);
System.out.println("The queue is: " + priority);
}When that function is run, the output is:
As you can see, the order of elements in this queue is not the order they are added.
From the result, you might think that Priorityqueue orders the elements in the queue..
But this is a fatal misconception!
PriorityQueue doesn’t guarantee the order of elements. It guarantees the order of elements when you remove them from the queue.
Consider this example:
private static void priorityQueueExampleString() {
PriorityQueue<String> priority = new PriorityQueue<>(String::compareTo);
priority.offer("Zed");
priority.offer("Karen");
priority.offer("Abby");
System.out.println("The queue is: " + priority);
System.out.println(priority.remove());
System.out.println(priority.remove());
System.out.println(priority.remove());
}You might expect that the line “The queue is: …” would print “Abby, Karen, Zed” in that order. However, that’s not the case.
Run the code and here is the output:
As you can see, the elements in the queue are not ordered alphabetically as you might expect. However, when we called the function remove, the order of items displayed correctly according to their alphabetic order.
Put another way, the highest priority element in the priority queue will be removed first.
You cannot add null to a priority queue.
Priority queue of a custom object
Let’s consider this simple object:
package com.datmt.java_core.collection.queue.priority;
public class People {
private String name;
public People(String name) {
this.name = name;
}
public String getName() {
return name;
}
@Override
public String toString() {
return "People[name=" + name + "]";
}
}
How can we create a priority queue for this type?
You can create a function like this and it compiles just fine:
private static void priorityQueueCustomObject() {
PriorityQueue<People> people = new PriorityQueue<>();
people.offer(new People("Jake"));
people.offer(new People("Kim"));
people.offer(new People("Lee"));
System.out.println(people.remove());
}However, this code will throw ClassCastException. Why?
Since we are using a priority queue, there must be a mechanism to assign priority to the elements. The compiler in this case doesn’t know how to assign priority to a People instance.
What can we do?
Well, either
- make the People class implement Comparable or
- provide a Comparator in the PriorityQueue constructor.
We are going to implement both here.
Provide a Comparator
Let’s say we order people by their name.
private static void priorityQueueCustomObjectUsingComparator() {
PriorityQueue<People> people = new PriorityQueue<>(Comparator.comparing(People::getName));
people.offer(new People("Aaron"));
people.offer(new People("Zed"));
people.offer(new People("Chris"));
System.out.println(people.remove());
System.out.println(people.remove());
System.out.println(people.remove());
}This is the output, as you might expect:
The benefit of this method is you don’t need to modify the People class. We only need to provide a Comparator in the queue’s constructor.
Implement the Comparable interface
Instead of providing a Comparator, we can solve the issue by making the People class implement the Comparable interface.
The People class now looks like this:
package com.datmt.java_core.collection.queue.priority;
public class People implements Comparable<People> {
private String name;
public People(String name) {
this.name = name;
}
public String getName() {
return name;
}
@Override
public String toString() {
return "People[name=" + name + "]";
}
@Override
public int compareTo(People people) {
return name.compareTo(people.getName());
}
}
Then, we can implement a priority queue of people without providing a comparator:
private static void priorityQueueCustomObjectUsingComparableInterface() {
PriorityQueue<People> people = new PriorityQueue<>();
people.offer(new People("Aaron"));
people.offer(new People("Zed"));
people.offer(new People("Chris"));
System.out.println(people.remove());
System.out.println(people.remove());
System.out.println(people.remove());
}This approach works just like the other.
Using priority queue with Concurrent code
If your queue is accessed, or modified by multiple threads, PriorityQueue is not a good option. Instead, you would consider the thread-safe implementation of the priority queue PriorityBlockingQueue
Let’s consider this concurrent code that use PriorityQueue and see the problem:
private static void nonSafePriorityQueue() throws InterruptedException {
PriorityQueue<Integer> queue = new PriorityQueue<>();
ExecutorService executorService = Executors.newFixedThreadPool(10);
//adding 20 elements
for (int i = 0; i < 20; i ++) {
int finalI = i;
executorService.submit(() -> queue.offer(finalI));
}
executorService.shutdown();
executorService.awaitTermination(10, TimeUnit.SECONDS);
System.out.println("queue: " + queue + " has " + queue.size() + " items");
}When you run this code, the final queue sometimes has 17 items, sometimes has 18 items…
You may have a totally different result.
Here are the results after some executions:
Now, let’s switch to the same code but use PriorityBlockingQueue
private static void safePriorityQueue() throws InterruptedException {
PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>();
ExecutorService executorService = Executors.newFixedThreadPool(10);
//adding 20 elements
for (int i = 0; i < 20; i ++) {
int finalI = i;
executorService.submit(() -> queue.offer(finalI));
}
executorService.shutdown();
executorService.awaitTermination(10, TimeUnit.SECONDS);
System.out.println("queue: " + queue + " has " + queue.size() + " items");
}The order of items in queue could be different between executions, however, the queue always has 20 items from 0 to 19 as you expect:
Similar to PriorityQueue, you cannot add null to PriorityBlockingQueue
Conclusion
In this post, we discussed the use of PriorityQueue, how to add custom objects to a queue and how can we handle the queue in multi-threaded code.
The code of this post is available here on Github.
I build softwares that solve problems. I also love writing/documenting things I learn/want to learn.