Have you ever worked in a restaurant that required you to store food items so that the items expiring soonest are the first to be used? If you have, you have already worked with a priority queue.
As the name “PriorityQueue” suggests, it’s an object meant to group and prioritize items in a queue. Normally, queues follow a First In, First Out (FIFO) structure like the restaurant example from earlier, but sometimes we might want to change the order of items in the queue to better reflect their importance.
In this article, we'll examine the PriorityQueue class in Java, show how it works, and give some examples of it in action. Click any of the links below to jump to that section.
What does PriorityQueue do in Java?
A PriorityQueue in Java holds a collection of objects together, much like an array. However, it contains ways to prioritize which elements are utilized first. This has many potential applications depending on what your priorities are and what the context is.
For example, say that you had a website selling products to customers. You’re watching the orders come in and notice you have a huge order with products that are not quite yet available in your inventory, followed by much smaller orders behind it with products that you could ship out immediately.
If your system is set up in a way that operates on a FIFO basis, this would effectively halt filling orders until the huge order is ready, creating a massive backlog, and likely frustrated customers. A PriorityQueue could avoid this problem by simply checking if the next order to be filled is actually ready yet, and pushing it back in the queue if not.
It doesn’t even have to be for customer orders either. If you were hosting a web service with limited processing power available, you could choose which customers get priority based on things like the computational complexity of their request or whether they’re a paid user.
Java PriorityQueue in Action
Considering that this is a back-end concept, it’s fairly difficult to know for sure if a website is using this object. However, it’s reasonable to assume that it could be going on behind the scenes in any website that has to prioritize the way it delivers services to clients.
One popular application for PriorityQueue is in the context of companies that have to split bandwidth for their service between users. Another example could be a company that assigns tasks to workers based on the priority of the task.
Despite the “catch” from above, you can still look at this picture to help solidify your understanding.
Essentially what you’re seeing is the process of adding an element with a priority of “45” into the queue between the elements with priorities “40” and “50.”
Elements with the lowest number in the queue are processed first, with the next element to be processed referred to as the “Front” or “Head” of the queue. Conversely, the “Back” or “Tail” of the queue would be the last element to be processed, assuming the ordering doesn’t change.
Referring back to the bandwidth management example, the above image could be a queue of a company with insufficient bandwidth to service all users simultaneously.
To deal with this issue, they could prioritize who to service next, perhaps based on whether they’re a local customer, what sort of access level they had, or anything other determining characteristic decided upon by the company managing bandwidth.
How to Use PriorityQueue in Java
In the following example, you are going to create a new PriorityQueue object, add some items to it, and learn how to investigate elements of the queue. Take a look at the following code.
- The first step in using the PriorityQueue object is, of course, to import the library containing the PriorityQueue class.
- The next step is to declare a variable to hold the PriorityQueue object. The PriorityQueue constructor can take a custom comparator (a way to compare the objects that are added).
- Once the object is created, you can begin adding objects. By using no arguments in the constructor, it will default to having a limit of 11 elements and prioritizing objects based on their natural order.
- Now, print the PriorityQueue.
- To retrieve the head element of the PriorityQueue, use the peek() method.
- To remove the head element, you should use the poll() method.
If left blank, it will default to processing according to natural priority. In the case of integers, this means that the smallest integer will be put at the head of the queue.
Integers will go smallest first, and strings will go smallest first in ASCII decimal value. Ignore the e: in the following code. It is merely a feature of the text editor that is not part of the code.
Since the PriorityQueue is heap based, the order might look random or unsorted when printing the whole thing out. Remember, you’re not dealing with a sorted array here. Things will still be prioritized based on natural order when you start examining the head of the PriorityQueue instead of printing it all out.
Despite the above order, the head elements would actually go in the following order, because the natural order of integers is least to greatest.
In this case, the above code will return the 3 at the front of the queue. Please note, however, that this will not remove the element. It will stay at the front of the queue even after calling this method.
This method is almost identical to the previous one, except it will remove the head element afterward. Also, note that this method will return null if the queue is empty.
And that’s the basic concept! However, using a custom comparator might be wise if you want to take things one step further. If you were to construct the PriorityQueue with a custom comparator like this
Then define it like this:
You would have a way of sorting the integers from least to greatest. This isn’t really any different from the natural order for integers, but understanding what’s going on here will be useful for creating your own custom comparators.
Essentially you are comparing two elements at a time, called leftHandSide and rightHandSide for ease of understanding. If both sides are equal, zero will be returned, resulting in no swapping of the elements.
In the case of the leftHandSide being less than the rightHandSide, there will still be no elements swapped.
That is to say, if you compare 10 and 20, the order of the elements would still be [10, 20]. Again, natural order for integers is least to greatest. Things finally get interesting here, however:
The final condition that could be possible is that leftHandSide is greater than rightHandSide. In this case, by returning "1", you are essentially telling the PriorityQueue, “Hey, swap these two elements.”
If leftHandSide was 20 and rightHandSide was 10, the order of elements would still be [10, 20] because the two elements would be swapped.
This example was a simple one using integers, but the conditions used to determine whether or not to swap the elements can be as complex as you would like them to be. If you were to swap the -1 and +1 from the above code, the order of the PriorityQueue would go from least to greatest, to greatest to least.
Getting Started with Java PriorityQueue
If you’re looking to easily prioritize data and group together like objects, let a PriorityQueue in Java do the heavy lifting. Start practicing by coding a basic function. From there, build PriorityQueue into the bones of your web applications.
