A priority queue in Java is a special type of queue wherein all the elements are ordered as per their natural ordering or based on a custom Comparator supplied at the time of creation.
The front of the priority queue contains the least element according to the specified ordering, and the rear of the priority queue contains the greatest element.
So when you remove an element from the priority queue, the least element according to the specified ordering is removed first.
The Priority Queue class is part of Java’s collections framework and implements theQueue interface. Following is the class hierarchy of the Priority Queue class in Java.
Creating a Priority Queue
Let’s create a Priority Queue of integers and add some integers to it. After adding the integers, we’ll remove them one by one from the priority queue and see how the smallest integer is removed first followed by the next smallest integer and so on.
import java.util.PriorityQueue;
public class CreatePriorityQueueExample {
public static void main(String[] args) {
// Create a Priority Queue
PriorityQueue<Integer> numbers = new PriorityQueue<>();
// Add items to a Priority Queue (ENQUEUE)
numbers.add(750);
numbers.add(500);
numbers.add(900);
numbers.add(100);
// Remove items from the Priority Queue (DEQUEUE)
while (!numbers.isEmpty()) {
System.out.println(numbers.remove());
}
}
}
# Output
100
500
750
900
Let’s see the same example with a Priority Queue of String elements.
import java.util.PriorityQueue;
public class CreatePriorityQueueStringExample {
public static void main(String[] args) {
// Create a Priority Queue
PriorityQueue<String> namePriorityQueue = new PriorityQueue<>();
// Add items to a Priority Queue (ENQUEUE)
namePriorityQueue.add("Lisa");
namePriorityQueue.add("Robert");
namePriorityQueue.add("John");
namePriorityQueue.add("Chris");
namePriorityQueue.add("Angelina");
namePriorityQueue.add("Joe");
// Remove items from the Priority Queue (DEQUEUE)
while (!namePriorityQueue.isEmpty()) {
System.out.println(namePriorityQueue.remove());
}
}
}
# Output
Angelina
Chris
Joe
John
Lisa
Robert
In this case, the smallest String as per the natural ordering of Strings is removed first.
Creating a Priority Queue with a custom Comparator
Let’s say that we need to create a priority queue of String elements in which the String with the smallest length is processed first.
We can create such a priority queue by passing a custom Comparator that compares two Strings by their length.
Here is an example –
import java.util.Comparator;
import java.util.PriorityQueue;
public class PriorityQueueCustomComparatorExample {
public static void main(String[] args) {
// A custom comparator that compares two Strings by their length.
Comparator<String> stringLengthComparator = new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
};
/*
The above Comparator can also be created using lambda expression like this =>
Comparator<String> stringLengthComparator = (s1, s2) -> {
return s1.length() - s2.length();
};
Which can be shortened even further like this =>
Comparator<String> stringLengthComparator = Comparator.comparingInt(String::length);
*/
// Create a Priority Queue with a custom Comparator
PriorityQueue<String> namePriorityQueue = new PriorityQueue<>(stringLengthComparator);
// Add items to a Priority Queue (ENQUEUE)
namePriorityQueue.add("Lisa");
namePriorityQueue.add("Robert");
namePriorityQueue.add("John");
namePriorityQueue.add("Chris");
namePriorityQueue.add("Angelina");
namePriorityQueue.add("Joe");
// Remove items from the Priority Queue (DEQUEUE)
while (!namePriorityQueue.isEmpty()) {
System.out.println(namePriorityQueue.remove());
}
}
}
# Output
Joe
John
Lisa
Chris
Robert
Angelina
Notice how the String with the smallest length is removed first.
Priority Queue of user-defined objects
In this example, you’ll learn how to create a priority queue of user-defined objects.
Since a priority queue needs to compare its elements and order them accordingly, the user-defined class must implement the Comparable interface, or you must provide a Comparatorwhile creating the priority queue. Otherwise, the priority queue will throw a ClassCastExceptionwhen you add new objects to it.
Check out the following example in which we create a priority queue of a custom class called Employee. The Employee class implements the Comparable interface and compares two employees by their salary.
import java.util.Objects;
import java.util.PriorityQueue;
class Employee implements Comparable<Employee> {
private String name;
private double salary;
public Employee(String name, double salary) {
this.name = name;
this.salary = salary;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
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 "Employee{" +
"name='" + name + '\'' +
", salary=" + salary +
'}';
}
// Compare two employee objects by their salary
@Override
public int compareTo(Employee employee) {
if(this.getSalary() > employee.getSalary()) {
return 1;
} else if (this.getSalary() < employee.getSalary()) {
return -1;
} else {
return 0;
}
}
}
public class PriorityQueueUserDefinedObjectExample {
public static void main(String[] args) {
/*
The requirement for a PriorityQueue of user defined objects is that
1. Either the class should implement the Comparable interface and provide
the implementation for the compareTo() function.
2. Or you should provide a custom Comparator while creating the PriorityQueue.
*/
// Create a PriorityQueue
PriorityQueue<Employee> employeePriorityQueue = new PriorityQueue<>();
// Add items to the Priority Queue
employeePriorityQueue.add(new Employee("Rajeev", 100000.00));
employeePriorityQueue.add(new Employee("Chris", 145000.00));
employeePriorityQueue.add(new Employee("Andrea", 115000.00));
employeePriorityQueue.add(new Employee("Jack", 167000.00));
/*
The compareTo() method implemented in the Employee class is used to determine
in what order the objects should be dequeued.
*/
while (!employeePriorityQueue.isEmpty()) {
System.out.println(employeePriorityQueue.remove());
}
}
}
# Output
Employee{name='Rajeev', salary=100000.0}
Employee{name='Andrea', salary=115000.0}
Employee{name='Chris', salary=145000.0}
Employee{name='Jack', salary=167000.0}
Notice how the Employee with the lowest salary is removed first.
Conclusion
In this article, you learned what is a priority queue, how to use a priority queue, how to create a priority queue with a custom comparator, and how to have user-defined objects in a priority queue.
Thanks for reading folks. See you next time! This article is from callicoder
