In Java, a priority queue is a special form of the queue in which all components are ordered either by their natural ordering or by a custom Comparator provided at the time of construction. Before talking about priority queues, let’s look at what a regular queue is.
The first in, first out (FIFO) structure is used in a typical queue. If three messages – m1, m2, and m3 – enter the queue in that sequence, they will exit in the same order.
What is the purpose of queues?
Let’s imagine we have highly fast data generators (for example, when a user clicks on a web page). However, we intend to ingest this data more slowly later. In this scenario, the producer would send all of the messages to the queue, and a consumer would consume them at a slower rate later from the queue.
According to the given ordering, the front of the priority queue includes the least element, and the back of the priority queue has the greatest element.
According to the stated ordering, the least important element is removed first on removing an element from the priority queue. The Priority Queue class implements the Queue interface and is part of Java’s collections system. The Priority Queue class in Java has the following class structure.
The following are some key factors to remember about Priority Queue:
- Null is not allowed in PriorityQueue.
- We can’t establish a PriorityQueue of non-comparable objects.
- Unbound queues are PriorityQueues.
- The last entry in the specified ordering is at the head of this queue. If there are numerous components tied for the lowest value, the head is one of the – ties broken at random.
- Because PriorityQueue isn’t thread-safe, Java provides a workaround.
- In a Java multithreading environment, the PriorityBlockingQueue class implements the BlockingQueue interface.
- The poll, delete, peek, and element procedures all access the element at the top of the queue.
- The add and poll techniques take O(log(n)) time.
- AbstractQueue, AbstractCollection, Collection, and Object all have methods that it inherits.
Putting Together a Priority Queue
Let’s construct an integer Priority Queue and add some integers to it. After adding the integers to the priority queue, we’ll remove them to notice how the smallest integer gets deleted first, then the next smallest integer, and so on.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.PriorityQueue;
public class CodePriorityQueue {
public static void main(String[] args) {
// Create a Priority Queue
PriorityQueue<Integer> numPQ = new PriorityQueue<>();
// Add items to a Priority Queue (ENQUEUE)
numPQ.add(120);
numPQ.add(90);
numPQ.add(10);
numPQ.add(89);
// Removing Priority Queue (DEQUEUE) items
while (!numPQ.isEmpty()) {
System.out.println(numPQ.remove());
}
}
}</pre>
</div>
Let’s look at the identical scenario using a String Priority Queue.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.PriorityQueue;
public class CodePriorityQueueString {
public static void main(String[] args) {
// Creation of a Priority Queue
PriorityQueue<String> stringPQ = new PriorityQueue<>();
// Add items to a Priority Queue (ENQUEUE)
stringPQ.add("Apple");
stringPQ.add("Mango");
stringPQ.add("Quava");
stringPQ.add("Pineapple");
stringPQ.add("Banana");
stringPQ.add("Peas");
// Removing Priority Queue (DEQUEUE) Items
while (!stringPQ.isEmpty()) {
System.out.println(stringPQ.remove());
}
}
}</pre>
</div>
In this scenario, the smallest String gets deleted first, as per the natural ordering of Strings.
Using a custom Comparator to create a Priority Queue
Assume that we need to establish a priority queue of String items, with the shortest String being processed first. We may establish such a priority queue by passing a custom Comparator that compares two Strings by length. Here’s an illustration:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.Comparator;
import java.util.PriorityQueue;
public class CodePriorityQueueCustomComparator {
public static void main(String[] args) {
// A custom comparator that compares the lengths of two Strings.
Comparator<String> strLengthComparator = new Comparator<String>() {
@Override
public int compare(String strOne, String strTwo) {
return strOne.length() - strTwo.length();
}
};
/*
A lambda expression like this can be used to build the above Comparator=>
Comparator<String> strLengthComparator = (strOne, strTwo) -> {
return strOne.length() - strTwo.length();
};
Which can be condensed even more in the following way: =>
Comparator<String> strLengthComparator = Comparator.comparingInt(String::length);
*/
// Create a custom Comparator for a Priority Queue.
PriorityQueue<String> laptopPQ = new PriorityQueue<>(stringLengthComparator);
// Add items to a Priority Queue (ENQUEUE)
laptopPQ.add("HP");
laptopPQ.add("DELL");
laptopPQ.add("IBM");
laptopPQ.add("Chrome Book");
laptopPQ.add("Lenovo");
laptopPQ.add("Toshiba");
// Removing Priority Queue (DEQUEUE) Items
while (!laptopPQ.isEmpty()) {
System.out.println(laptopPQ.remove());
}
}
}</pre>
</div>
Take notice of how the shortest string gets deleted first.
User-defined object priority queue
Custom orders are also available, and we can accomplish so with the assistance of a comparator. Let’s start by making an integer priority queue. But this time, let’s sort the results by value in descending order. To accomplish this, we must first construct an integer comparator:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre> static class CodeCustomIntegerComparator implements Comparator<Integer> {
@Override
public int compare(Integer intOne, Integer intTwo) {
return intOne < intTwo ? 1 : -1;
}
}
</pre>
</div>
We implement the comparator interface and override the compare method to create a comparator. We may retrieve the result in descending order by using intOne< intTwo? 1: -1. The results would have been in increasing order if we had used intOne > intTwo? 1: -1. We need to add the comparator to the priority queue now that we’ve got it. This is how we can accomplish it:
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>Queue<Integer> codeIntPQ = new PriorityQueue<>(new CustomIntegerComparator());</pre> </div>
The remaining code, which adds elements to the priority queue and prints them, is as follows:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>codeIntPQ.add(11);
codeIntPQ.add(5);
codeIntPQ.add(-1);
codeIntPQ.add(12);
codeIntPQ.add(6);
System.out.println("In a Priority Queue, integers are kept in reverse order of priority. \n");
while (!codeIntPQ.isEmpty()) {
System.out.println(codeIntPQ.poll());
}</pre>
</div>
We can observe that the comparator did a good job. The integers are now being delivered in descending order via the priority queue. In this example, you’ll learn how to create a priority queue of user-defined items.
Because a priority queue must compare and organize its contents, the user-specified class must implement the Comparable interface. Or a Comparator must be provided when the priority queue is created. If you add new objects to the priority queue, it will throw a ClassCastException.
Take a look at the example below, in which we establish a priority queue for a custom class called Employee. The Employee class uses the Comparable interface to compare the salaries of two employees.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.Objects;
import java.util.PriorityQueue;
class CodeEmployee implements Comparable<Employee> {
private String fName;
private String mName;
private double salary;
public CodeEmployee(String fName, String mName, double salary) {
this.fName = fName;
this.mName = mName;
this.salary = salary;
}
public String getFName() {
return fName;
}
public void setFName(String fName) {
this.fName = fName;
}
public String getMName() {
return mName;
}
public void setMName(String mName) {
this.mName = mName;
}
public double getSalary() {
return salary;
}
public void setSalary(double salary) {
this.salary = salary;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Employee employee = (Employee) o;
return Double.compare(employee.salary, salary) == 0 &&
Objects.equals(name, employee.name);
}
@Override
public int hashCode() {
return Objects.hash(name, salary);
}
@Override
public String toString() {
return "CodeEmployee{" +
"name='" + name + '\'' +
", salary=" + salary +
'}';
}
// Comparing two code employee objects based on their salaries
@Override
public int compareTo( CodeEmployee cEmployee) {
if(this.getSalary() > cEmployee.getSalary()) {
return 1;
} else if (this.getSalary() < employee.getSalary()) {
return -1;
} else {
return 0;
}
}
}
public class UserDefinedPriorityQueueObject {
public static void main(String[] args) {
/*
A PriorityQueue with user-defined items is required because
1. Either the Comparable interface should be implemented, or the compareTo() function should be implemented.
2. Alternatively, while constructing the PriorityQueue, you should give a custom Comparator.
*/
// Create a PriorityQueue
PriorityQueue<CodeEmployee> employeePQ = new PriorityQueue<>();
// Add items to the Priority Queue
employeePQ.add(new CodeEmployee("Ken", 90000.00));
employeePQ.add(new CodeEmployee("Joy", 190000.00));
employeePQ.add(new CodeEmployee("Paul", 55000.00));
employeePQ.add(new CodeEmployee("Green", 37000.00));
/*
The Employee class's compareTo() method establishes the order in which the objects should be dequeued.
*/
while (!employeePQ.isEmpty()) {
System.out.println(employeePQ.remove());
}
}
}</pre>
</div>
Take note of how the code employee with the lowest wage is the first to be fired.
Java Objects in a priority queue
We’ve seen how to use strings and integers with priority queues up to this point. Priority queues containing custom Java objects are commonly used in real-world applications. Let’s start by making an EcommerceOrder class to hold customer order information:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>public class EcommerceOrder implements Comparable<EcommerceOrder> {
private int ordId;
private double ordAmount;
private String customerName;
public EcommerceOrder(int ordId, double ordAmount, String customerName) {
this.ordId = ordId;
this.orderAmount = ordAmount;
this.customerName = customerName;
}
@Override
public int compareTo( EcommerceOrder o) {
return o.orderId > this.ordId? 1 : -1;
}
@Override
public String toString() {
return "ordId:" + this.ordId + ", ordAmount:" + this.ordAmount + ", customerName:" + customerName;
}
public double getOrderAmount() {
return ordAmount;
}
}
</pre>
</div>
It is a straightforward Java class for keeping track of customer orders. This class implements a similar interface, allowing us to choose how this item should be prioritized in the priority queue. The compareTo function in the above code determines the ordering. The line o.ordId > this.ordId ?1: -1 specifies that the orders should be sorted in the ordId field’s decreasing order.
The code that builds a priority queue for the EcommerceOrder object is as follows:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>EcommerceOrder ecommerceOrder1 = new EcommerceOrder(1, 189.0, "Client One");
EcommerceOrder ecommerceOrder2 = new EcommerceOrder(3, 87.0, "Client Three");
EcommerceOrder ecommerceOrder3 = new EcommerceOrder(2, 260.0, "Client Two");
Queue<EcommerceOrder> ecommerceClientOrders = new PriorityQueue<>();
ecommerceClientOrders.add(ecommerceOrder1);
ecommerceClientOrders.add(ecommerceOrder2);
ecommerceClientOrders.add(ecommerceOrder3);
while (!ecommerceClientOrders.isEmpty()) {
System.out.println(ecommerceClientOrders .poll());
}</pre>
</div>
Three e-commerce orders have been made and added to the priority queue in the code above. We receive the following output when we run this code:
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>ordId:3, ordAmount:87.0, customerName: Client Three ordId:2, ordAmount:260.0, customerName: Client Two ordId:1, ordAmount:189.0, customerName: Client One</pre> </div>
The result is in descending order of ordId, as intended.
Prioritizing based on the ordAmount parameter
This is yet another true story. Let’s say the ordId prioritizes the eCommerceClientOrder object by default. However, we’ll need the means to prioritize based on orderAmount. You might imagine that we can edit the eCommerceOrder class’s compareTo function to order based on ordAmount.
However, because the eCommerceOrder class is used in various locations throughout the application, changing the compareTo function directly would cause problems elsewhere. The answer is simple: we can construct a new custom comparator for the eCommerceOrder class and use it in conjunction with the priority queue. The code for the custom comparator is as follows:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre> static class eCommerceOrderComparator implements eCustomComparator<EcommerceOrder> {
@Override
public int compare( EcommerceOrder ordOne, EcommerceOrder ordTwo)
{
return ordOne.getOrderAmount() < ordTwo.getOrderAmount() ? 1 : -1;
}
}</pre>
</div>
It looks a lot like the custom integer comparator we saw before.
The line ordOne.getOrderAmount() < ordTwo.getOrderAmount()? 1: -1; shows that we must prioritize according to orderAmount in decreasing order. The code that constructs the priority queue is as follows:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre> EcommerceOrder eCommerceOne = new EcommerceOrder(1, 100.0, "eCommerce Client1");
EcommerceOrder eCommerceTwo = new EcommerceOrder(3, 50.0, "eCommerce Client3");
EcommerceOrder eCommerceThree = new EcommerceOrder(2, 300.0, "eCommerce Client2");
Queue<EcommerceOrder> eClientOrders = new PriorityQueue<>(new CustomerOrderComparator());
eClientOrders.add(eCommerceOne);
eClientOrders.add(eCommerceTwo);
eClientOrders.add(eCommerceThree);
while (!eClientOrders.isEmpty()) {
System.out.println(eClientOrders.poll());
}</pre>
</div>
In the preceding code, the comparator is passed to the priority queue in the next line:
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>Queue<EcommerceOrder> eClientOrders = new PriorityQueue<>(new eCommerceOrderComparator());</pre> </div>
After running this code, we get the following result:
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>ordId:2, ordAmount:300.0, customerName:customer2 ordId:1, ordAmount:100.0, customerName:customer1 ordId:3, ordAmount:50.0, customerName:customer3</pre> </div>
We can see that the data is sorted by ordAmount in descending order.
Java’s Minimum Priority Queue
The least or smallest element is at the front of the queue in the natural ordering of the Priority Queue. As a result, the ordering is ascending. With ascending order of components, this is known as the “Min priority queue.” The Java program below demonstrates how the Min Priority Queue is implemented in Java.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.*;
class Main{
public static void main(String args[]){
//Create a PriorityQueue object with the default ordering.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
// add a priority queue element
priorityQueue.add(18);
priorityQueue.add(16);
priorityQueue.add(14);
priorityQueue.add(12);
priorityQueue.add(22);
priorityQueue.add(20);
//show the minimum PriorityQueue
System.out.println("The minimum contents of the Priority Queue (natural ordering):");
Integer val = null;
while( (val = priorityQueue.poll()) != null) {
System.out.print(val + " ");
}
}
}</pre>
</div>
Java’s Maximum Priority Queue
The elements in the min priority queue are in ascending order. In contrast, the elements in the max priority queue are in descending order, i.e. the head of the Max priority queue returns the greatest element in the queue. The code snippet below shows how to use the Java Max Priority Queue.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.*;
class Main{
public static void main(String args[]){
//To generate the maximum PQ, declare a PriorityQueue object with a custom comparator.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer lhs, Integer rhs) {
if (lhs < rhs) return +1;
if (lhs.equals(rhs)) return 0;
return -1;
}
});
//add element to the PriorityQueue
priorityQueue.add(8);
priorityQueue.add(6);
priorityQueue.add(4);
priorityQueue.add(2);
priorityQueue.add(12);
priorityQueue.add(10);
//showing the max PriorityQueue
System.out.println("The max Priority Queue contents:");
Integer val = null;
while( (val = priorityQueue.poll()) != null) {
System.out.print(val + " ");
}
}
}</pre>
</div>
Example: Natural ordering priority queues
Here’s some code that demonstrates how to make a simple string priority queue.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>private static void CodeStringNaturalOrdering() {
Queue<String> codeStringsPQ = new PriorityQueue<>();
codeStringsPQ.add("mango");
codeStringsPQ.add("apple");
codeStringsPQ.add("banana");
codeStringsPQ.add("peas");
codeStringsPQ.add("quavas");
System.out.println("Strings in a Priority Queue Stored in Natural Order \n");
while (!codeStringsPQ.isEmpty()) {
System.out.println(codeStringsPQ.poll());
}
}</pre>
</div>
Example: Priority Queues in Java
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>package com.code.underscored;
import java.util.PriorityQueue;
public class CodePriorityQueue {
public static void main(String[] args) {
// Create a PriorityQueue to sort things according to their natural order.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// Let's fill in some gaps in the PriorityQueue.
Integer [] elements = new Integer[]{108, 200, 198, 110, 102,
115, 145, 125, 176, 103, 109, 101, 163, };
for (int e: elements) {
priorityQueue.add(e);
}
// Let's go over the elements one by one to see if they're all stored in the same order.
System.out.print("Iterative printing: ");
for(int e: priorityQueue) {
System.out.print(e + " ");
}
System.out.println();
System.out.print("Retrieval Printing: ");
// Remove each element one by one.
while (!priorityQueue.isEmpty()) {
System.out.print(priorityQueue.remove() + " ");
}
}
}</pre>
</div>
We added a few integers to the queue in any order in the example above. The components were then printed once I iterated over the queue. As you can see above, the items are not saved in sorted order. As previously stated, binary heap only guarantees semi-ordering: elements in upper nodes are more (or fewer) than those in lower nodes. For example, in a max-heap, parents are always greater than their children. Heaps, unlike Binary Search Trees, do not keep absolute left-to-right ordering.
Example: Priority Queue Comparator
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.*;
public class Main {
public static void main(String[] args) {
// A custom comparator that compares the lengths of two Strings.
Comparator<String> codeComparator = new Comparator<String>() {
@Override
public int compare(String strOne, String strTwo) {
return strOne.length() - strTwo.length();
}
};
// Creation of a custom Comparator for a Priority Queue.
PriorityQueue<String> fruitsPQ = new PriorityQueue<>(codeComparator);
// Addition of items to a Priority Queue
fruitsPQ.add("Apple");
fruitsPQ.add("Mango");
fruitsPQ.add("Peas");
fruitsPQ.add("Guava");
fruitsPQ.add("Banana");
fruitsPQ.add("Lemon");
// Printing all elements
System.out.println("\nThe PriorityQueue elements with custom Comparator:");
Iterator iter = fruitsPQ.iterator();
while (iter.hasNext())
System.out.print(iter.next() + " ");
}
}</pre>
</div>
Example: methods of PriorityQueue using a Java program
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.*;
class Codeunderscored {
public static void main(String args[]) {
// Creating empty priority queue
PriorityQueue<String> numPQ = new PriorityQueue<String>();
// add elements to numQueue using add()
numPQ.add("Five");
numPQ.add("One");
numPQ.add("Seven");
numPQ.add("Three");
numPQ.add("Eleven");
numPQ.add("Nine");
// Print the head element using Peek () method
System.out.println("Head element is using the peek method:" + numPQ.peek());
// Printing all elements
System.out.println("\n\nThe PriorityQueue elements:");
Iterator iter = numPQ.iterator();
while (iter.hasNext())
System.out.print(iter.next() + " ");
// remove head with poll ()
numPQ.poll();
System.out.println("\n\nAfter removing an element" + "with poll function:");
Iterator<String> iterTwo = numPQ.iterator();
while (iterTwo.hasNext())
System.out.print(iterTwo.next() + " ");
// Removing 'five' using the method remove ()
numQueue.remove("five");
System.out.println("\n\nElement 'five' with"
+ " remove function:");
Iterator<String> iterThree = numQueue.iterator();
while (iterThree.hasNext())
System.out.print(iterThree.next() + " ");
// Use contains to see if an element is present in PriorityQueue ()
boolean ret_val = numPQ.contains("Five");
System.out.println("\n\nPriority queue contains 'Five' "
+ "or not?: " + ret_val);
// toArray returns the array equivalent of PriorityQueue ()
Object[] numArr = numPQ.toArray();
System.out.println("\nArray Contents: ");
for (int i = 0; i < numArr.length; i++)
System.out.print(numArr[i].toString() + " ");
}
}
</pre>
</div>
Conclusion
In this article, you learned what a priority queue is, how to utilize one, how to create one with a custom comparator, and how to include user-defined objects in a priority queue.
A PriorityQueue is a queue type that allows Java programmers to insert components in any order but retrieve them in a predefined (sorted) order. The priority queue’s elements are sorted using a Comparator provided when the queue was built.
PriorityQueue is a valuable built-in collection that should be familiar to all Java developers. You’ll have an additional tool in your toolkit to design efficient applications once you’ve learned it.
When learning about priority queues, it’s crucial to understand the fundamental ideas, which are quite simple and help you make informed design decisions.
