PriorityQueue in Java
A PriorityQueue is a useful data structure in Java that allows objects to be processed based on their priority. While a traditional queue follows the First-In-First-Out algorithm, the PriorityQueue comes in handy when elements need to be processed based on their priority. The PriorityQueue is based on the priority heap, where the elements are ordered according to the natural ordering or a Comparator provided at queue construction time, depending on which constructor is used.
Here are some important points to remember about PriorityQueue:
- PriorityQueue in Java implements the Heap data structure by default.
- PriorityQueue does not allow null values.
- It is not possible to create a PriorityQueue of non-comparable objects.
- PriorityQueue is an unbound queue.
- The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements. Ties are broken arbitrarily.
- The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
- It inherits methods from the AbstractQueue, AbstractCollection, Collection, and Object classes.
Basic Operations on PriorityQueue:
- boolean add(E element): This method inserts the specified element into the priority queue.
- public peek(): This method retrieves, but does not remove, the head of the queue, or returns null if the queue is empty.
- public poll(): This method retrieves and removes the head of the queue, or returns null if the queue is empty.
Example 1: Uses the default min-Heap to implement the PriorityQueue.
// Java program to demonstrate working of
// PriorityQueue in Java
import java.util.*;
class Test{
public static void main(String args[])
{
// Creating an empty priority queue
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// Adding items to the priority queue using add()
pq.add(10);
pq.add(20);
pq.add(15);
// The above PriorityQueue is stored as follows:
// 10
// / \
// 20 15
// Printing the top element of the priority queue
System.out.println(pq.peek());
// Printing the top element and removing it from the priority queue
System.out.println(pq.poll());
// After poll(), the PriorityQueue looks like this:
// 15
// /
// 20
// Printing the top element again
System.out.println(pq.peek());
}
}
Output:
10
10
15
Example 2: Uses the max-Heap to implement the PriorityQueue.
// Java program to demonstrate working of
// PriorityQueue in Java
import java.util.*;
class Test{
public static void main(String args[])
{
// Creating an empty priority queue
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(
Collections.reverseOrder());
// Adding items to the priority queue using add()
pq.add(10);
pq.add(20);
pq.add(15);
// The above PriorityQueue is stored as follows:
// 20
// / \
// 10 15
// Printing the top element of the priority queue
System.out.println(pq.peek());
// Printing the top element and removing it from the priority queue
System.out.println(pq.poll());
// After poll(), the PriorityQueue looks like this:
// 15
// /
// 10
// Printing the top element again
System.out.println(pq.peek());
}
}
Output:
20
20
15
In summary, PriorityQueue is a useful data structure that can be used when objects need to be processed based on priority
To use the PriorityQueue with a custom ordering, we can provide a Comparator when creating the queue. For example, if we want to process Strings in descending order of length, we can create a PriorityQueue like this:
PriorityQueue<String> queue = new PriorityQueue<>(Comparator.comparing(String::length).reversed());
Now, when we add Strings to the queue, they will be ordered by length in descending order:
queue.add("hello");
queue.add("world");
queue.add("Java");
queue.add("PriorityQueue");
The head of the queue (returned by peek() or poll()) will be the String with the longest length. In this case, "PriorityQueue" is the head.
We can also create a PriorityQueue of custom objects, as long as those objects are comparable or a custom Comparator is provided. For example, let's say we have a class Person with name and age fields. We can create a PriorityQueue of Persons like this:
class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public int compareTo(Person o) {
return Integer.compare(age, o.getAge());
}
}
Now we can create a PriorityQueue of Persons, and they will be ordered by age:
PriorityQueue<Person> queue = new PriorityQueue<>();
queue.add(new Person("Alice", 25));
queue.add(new Person("Bob", 30));
queue.add(new Person("Charlie", 20));
The head of the queue (returned by peek() or poll()) will be the Person with the lowest age. In this case, it is Charlie.
In summary, the PriorityQueue in Java is a powerful data structure that allows efficient processing of elements based on priority. It can be used with natural ordering or custom ordering, and with built-in or custom objects.