PriorityQueue is a built-in Java collection. In this tutorial, we’ll first review what a priority queues are, and then how to work with priority queues in Java. Let’s go.
What is a Priority Queue?
Let’s start by looking at plain old queues.
A queue is an efficient data-structure (collection) for storing a number of objects. The objects can be added in any arbitrary order and the queue remembers and keeps the order in which they were added. It supports retrieving elements only from its head or tail, which means you can only remove by the very first element you inserted into the queue (or the very last one.) Queues are often used to distribute work to a pool of workers. They act as a buffer between producers who are producing work at a high rate, and a limited pool of workers who are carrying out the work. For example, ThreadPool library in Java uses a queue to hold tasks submitted to it and transfers them to worker threads when they become available.
In many use cases, the default order of the queue (first-in-first-out) is sufficient. If you’re submitting jobs or tasks to a ThreadPool that are all the same, it is often desirable to process them in the same order in which they were submitted. But there are times when you’d want to process a category of high-priority tasks before low-priority ones. Suppose, you’re receiving online orders from your users and storing them in a queue to be processed by available workers. With a vanilla queue, the orders will be processed in the order in which they arrived. Now imagine that you want to expedite orders from premium customers and process them first over regular customers. A regular queue won’t help you with this.
Enter priority queues. They are just like regular queues with one important difference: each element in the queue has a priority attached to it. Elements can be pulled in the order of priority. To store elements, a priority queue uses a data structure called binary heap. A binary heap is a self-organizing binary tree which adjusts itself each time elements are added or removed from it. In the case of min-heap, the smallest element (1) is always kept at the very top regardless of the order in which it was inserted.
It is important to call out that priority queues (binary heaps) do not store elements in absolute sorted order necessarily. It imposes semi-ordering for efficiency in terms of speed of insertion and retrieval. I’ll show this with an example by iterating through a priority queue.
For More Information on priority queues, read the CodeAhoy free book on priority queues.
Priority Queues in Java
A PriorityQueue is a type of queue which allows Java developers to insert elements in arbitrary order but retrieve them in a specific (sorted) order. The elements of the priority queue are ordered using a Comparator provided when the queue was created. Let’s look at a complete example.
package com.codeahoy.tutorial.datastructures;
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// Create a PriorityQueue that sorts elements
// by their natural ordering
PriorityQueue<Integer> pq = new PriorityQueue<>();
// Let's add some elements to the PriorityQueue
Integer [] elements = new Integer[]{8, 100, 98, 10, 2,
15, 45, 25, 76, 3, 9, 1, 63, };
for (int e: elements) {
pq.add(e);
}
// Let's iterate through the elements to see they
// are not necessarily stored in sorted order
System.out.print("Print by Iterating: ");
for(int e: pq) {
System.out.print(e + " ");
}
System.out.println();
System.out.print("Print by Retrieval: ");
// Let's remove elements one by one
while (!pq.isEmpty()) {
System.out.print(pq.remove() + " ");
}
}
}
Output
Print by Iterating: 1 3 2 25 8 15 45 100 76 10 9 98 63
Print by Retrieval: 1 2 3 8 9 10 15 25 45 63 76 98 100
In the example above, you can see that I added a few integers to the queue in arbitrary order. Then I iterated through the queue and printed the elements. Here you can see that the elements are not stored in a sorted order. This is because binary heap only guarantees semi-ordering as discussed above: elements in the higher nodes are greater (or less) than than the elements in lower nodes. For example in a max-heap, parents are always greater than their children, as can be seen in the image below. Unlike Binary Search Trees, heaps don’t maintains absolute left-to-right ordering.
PriorityBlocking Queue
PriorityBlockingQueue is a cousin of PriorityQueue in Java. It supports all the features of PriorityQueue and adds support for blocking operations. A blocking queue allow workers to ‘block’ or ‘wait’ if the queue is empty. They remain in the blocked state until new tasks arrive. Blocking queues are very convenient when building worker pools and are widely used by developers.
That’s all! In this post, we learned about priority queues and binary heap which it uses under the hood. If you need a refresher or more in-depth look at the heap data structure, I highly recommend that you watch the following video which does a pretty good job of covering this topic.
Image credits: By Ermishin - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=12251273