In this example, we shall demonstrate how to use the java.util.PriorityQueue Class. The PriorityQueue Class implements the contract defined through the Queue interface. The PriorityQueue is like other collections as in, it is unbounded and we can specify the starting size. Also, it is not threadsafe in a multi-threaded environment. PriorityQueue Class was introduced since Java 5.
For multi-threaded environment, consider using the
PriorityBlockingQueue class.PriorityQueue Class sorts the tasks assigned to it using either the natural order(i.e. by implementing Comparable) or by the custom defined Comparator Object.
PriorityQueue(int initialCapacity, Comparator comparator) constructor accepts an object of Comparator Class to sort the tasks.
Before offering elements to a sorted collection like
PriorityQueue, confirm if the element is not null. Null elements cannot be sorted and hence, an ugly NullPointerException is thrown.Let’s take a look at how the PriorityQueue Class works and how it can be used.
Request.java:
package com.javacodegeeks.examples.bean;
public class Request implements Comparable<Request>
{
private String requestName = "";
private int priorityStatus = 0;
/**
* @param requestName
* @param priorityStatus
*/
public Request(String requestName, int priorityStatus)
{
this.requestName = requestName;
this.priorityStatus = priorityStatus;
}
@Override
public int compareTo(Request otherRequest)
{
return Integer.compare(priorityStatus, otherRequest.priorityStatus);
}
@Override
public String toString()
{
return "Request [requestName= " + requestName + ", priorityStatus=" + priorityStatus + "]";
}
}
PriorityQueueExample.java:
package com.javacodegeeks.examples.concurrent;
import java.util.PriorityQueue;
import com.javacodegeeks.examples.bean.Request;
/**
* @author Chandan Singh
*/
public class PriorityQueueExample
{
public static void main(String[] args)
{
PriorityQueue<Request> queueExample = new PriorityQueue<>();
queueExample.offer(new Request("ABC", 2));
queueExample.offer(new Request("ABC", 5));
queueExample.offer(new Request("ABC", 1));
while(!queueExample.isEmpty())
System.out.println(queueExample.poll());//remove and print the top element
}
}
OUTPUT:
Request [requestName= ABC, priorityStatus=1] Request [requestName= ABC, priorityStatus=2] Request [requestName= ABC, priorityStatus=5]
The generic class being put in PriorityQueue Object must have implemented either comparators or provide comparables objects to PriorityQueue. Failing to provide this(sorting mechanism) may lead to ClassCastException. Care should be taken while designing the comparators and comparables to avoid silent integer overflows, which may lead the program to exhibit non-deterministic behaviour. In case of ties for priority, the tasks are arbitrarily chosen.
We can also add other collection objects to the queue using the PriorityQueue(Collection c) constructor.
- Apart, from the methods used in the example above the
PriorityQueueClass offers a number of other utility methods, too.
E peek(): Returns the head of the queue but does not remove it likePoll()method. Comparator comparator(): Returns the comparator used by thePriorityQueue.Object toArray(): Returns the array of all tasks enqueued.int size(): Returns the number of elements enqueued inPriorityQueue.boolean contains(Object e): Returnstrueif the object is enqueued.boolean remove(Object e): Returnstrueand removes a single instance of thetaskpassed as argument.False, otherwise.void clear()Removes all the tasks enqueued.
Time Complexity :
Queueing & Removing from Queue : O(log n). (e.g. offer(),poll())
Searching : O(n)(e.g. contains())
Access : O(1)(e.g. size(), peek())
Conclusion :
Here, we tried to understand the use of PriorityQueue Class and how we can use the same when we have tasks that need to be executed in priority basis.
You can download the source code of this example here: PriorityQueueExample.zip
