Introduction
A Priority Queue in Java is an unbounded Queue based on a priority heap. The elements of the Priority Queue are ordered according to their natural ordering (when the object implements the Comparable interface), or by a Comparator provided during the priority queue construction time. In this post, we will learn about the Priority Queue in Java, its methods, and its application.
A brief introduction to a Queue
Since a Priority Queue is a Queue, I will briefly summarize the operations that can be performed on a Queue.
Queue methods
A Queue is a collection but provides additional methods for insertion, extraction and inspection. Each of these comes in two flavours: one throws an exception if the operation fails, while the other returns a special value (either null or false).
Insertion:
These methods add an element into the queue.
- add(Object): Throws IllegalStateException if there is no space to add the element.
- offer(Object): returns false if the element cannot be inserted into the queue (i.e., when it cannot be enqueued).
Removal:
It removes the element at the head of the queue and returns it.
- remove(): Throws NoSuchElementException if the queue is empty.
- poll(): Returns null if the queue is empty.
Inspection:
It returns the element at the head of the queue without removing it.
- element(): Throws NoSuchElementException if the queue is empty.
- peek(): Returns null if the queue is empty.
It depends on your use case or to decide which one to use.
Example: If the queue can never be empty when you attempt to remove/retrieve an element call the version that throws an exception. Or use the other version instead.
Priority Queue in Java
A Priority Queue is a Queue but orders the elements in the queue by a certain order. It is ordered such that the head of the queue is the least element with respect to the specified ordering. If multiple elements are tied for a position, the ties will be broken arbitrarily.
Internally, a priority queue uses an array to store the elements but the size of it in unbounded. If there is no space to add an element, it will create a new array with more space and move the existing elements into it. The details of the growth policy is unspecified.
There are two ways of specifying the ordering.
- Ordering by the natural ordering of the elements.
- Specifying a Comparator for ordering.
Note that when we pass a custom comparator, it overrides the natural ordering of the elements. Let us look at examples for each of these.
Priority Queue - Natural Ordering
We will create a Priority Queue consisting of String objects. A String has a natural ordering because it implements Comparator<String>. They are ordered lexicographically.
PriorityQueue<String> priorityQueue = new PriorityQueue<>();
priorityQueue.add("Michael");
priorityQueue.add("Adam");
priorityQueue.add("Mitch");
priorityQueue.add("Weiss");
priorityQueue.add("Kevin");
priorityQueue.add("Will");
The above code creates a PriorityQueue and adds a few names into it. The elements would be ordered lexicographically as
Adam -> Kevin -> Michael -> Mitch -> Weiss -> Will
We will explore the methods or operations that we can do on a Priority Queue in Java.
Inspection
The peek() or the element() method retrieves the head of the queue without removing it. Remember that the element() throws an NoSuchElementException if the queue is empty.
System.out.println(priorityQueue.peek()); //Adam
System.out.println(priorityQueue.element()); //Adam
These print Adam because it is the first element in the queue (head of the queue).
Removal
Let us remove two elements from the queue. We call this operation as dequeuing.
System.out.println(priorityQueue.remove()); //Adam
System.out.println(priorityQueue.poll()); //Kevin
We have used the remove() and the poll() method. Remember that the remove() method is stricter as it throws an exception if the queue is empty. The first dequeue returned Adam, and the second returned Kevin. Now, the head of the queue would have Michael.
System.out.println(priorityQueue.peek()); //Michael
Insertion
Let us add the removed elements back into the Queue.
priorityQueue.add("Adam");
priorityQueue.add("Kevin");
Since a priority queue is unbounded, both add() and the offer() methods are equivalent. Since the queue has string elements and are ordered lexicographically, the string ‘Adam’ would be at the head of the queue.
Let us now use a loop to remove (dequeue) all the elements from the queue till the queue is empty.
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.remove());
}
This prints,
Adam
Kevin
Michael
Mitch
Weiss
Will
Now the queue is empty. Calling peek() or poll() returns a null whereas calling element() or remove() throws a NoSuchElementException.
Priority Queue - Specifying a Comparator for ordering
Let us look at an example of having objects in a priority queue that have no natural ordering, i.e., the class does not implement Comparable.
In our example, there is a Customer class which has two fields viz., a name and a priority. The priority denotes how important the customer is. Assume that lower priority numbers have more importance.
public class Customer {
private String name;
private int priority;
private Customer(String name, int priority) {
this.name = name;
this.priority = priority;
}
public String getName() {
return name;
}
public int getPriority() {
return priority;
}
}
Let us create a priority queue and add a Customer object into it.
PriorityQueue<Customer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(new Customer("Adam", 3));
The add method throws a java.lang.ClassCastException stating that our Customer class cannot be cast to java.lang.Comparable.
There are two ways to fix it:
- Make the class implement Comparable.
- Pass a custom Comparator to specify how to order the elements.
Implementing Comparable
This is similar to our first example, where we had Strings in the queue. If we provide a natural ordering for the objects, the priority queue will use it for ordering. We can order the instances by the priority of the customer as,
public class Customer implements Comparable<Customer> {
private String name;
private int priority;
private Customer(String name, int priority) {
this.name = name;
this.priority = priority;
}
public String getName() {
return name;
}
public int getPriority() {
return priority;
}
@Override
public int compareTo(Customer o) {
return Integer.compare(priority, o.priority);
}
}
Passing a Custom Comparator
Another option is to pass a comparator as an argument to the Priority Queue constructor. Then it will use it to order the elements.
priorityQueue = new PriorityQueue<>((customer1, customer2)
-> Integer.compare(customer1.priority, customer2.priority));
Or, we can simplify this using one of the Comparator.comparing method as,
priorityQueue = new PriorityQueue<>(Comparator.comparingInt(customer -> customer.priority));
Now, let us add a few objects into the queue.
priorityQueue.add(new Customer("Adam", 3));
priorityQueue.add(new Customer("Mitch", 1));
priorityQueue.add(new Customer("Weiss", 2));
The queue has the customer objects ordered as shown below.
Mitch -> Weiss -> Adam
Mitch is at the head of the queue because he has the lowest priority number (highest priority for us; priority 1).
Specifying a Comparator overrides the natural ordering
What if we specify a custom comparator for objects that have a natural ordering?
The passed comparator will override or hide the natural ordering.
Let us queue strings and order them based on the string length from the shortest to the longest.
PriorityQueue<String> lengthBasedPriorityQueue =
new PriorityQueue<>(Comparator.comparingInt(String::length));
lengthBasedPriorityQueue.add("short string");
lengthBasedPriorityQueue.add("this is the longest string of all");
lengthBasedPriorityQueue.add("medium string");
lengthBasedPriorityQueue.add("this is a very long string");
lengthBasedPriorityQueue.add("a longer string");
The comparator Comparator.comparingInt(String::length) is a comparator that orders two Strings based on their length.
Let us dequeue the queue until it is empty to see the order in which the strings are placed.
while (!lengthBasedPriorityQueue.isEmpty()) {
System.out.println(lengthBasedPriorityQueue.remove());
}
short string
medium string
a longer string
this is a very long string
this is the longest string of all
Other constructors of Priority Queue
We have seen two overloaded constructors offered by a priority queue viz., one taking no arguments (relies on the natural ordering to order) and one that takes a custom comparator to order the elements. There are five other constructors.
Passing a collection
If we have a collection, we can pass it to the PriorityQueue constructor. If the collection is an instance of SortedSet or another PriorityQueue, it will order them by the same ordering as used by the SortedSet or the PriorityQueue. Otherwise it will order the elements in the passed collection according to the natural ordering of the elements. This means that the elements must implement the Comparable interface.
List<String> fruits = List.of("apple", "orange", "pear", "grapes");
PriorityQueue<String> fruitsQueue = new PriorityQueue<>(fruits);
//Ordered as
//apple -> grapes -> orange -> pear
If we pass a collection of elements that are not comparable, it will throw a ClassCastException.
Creating a PriorityQueue from a SortedSet
There is a constructor which accepts a SortedSet. The constructed priority queue will follow the same ordering as the given sorted set.
//Order by length breaking ties by ordering according to the name
SortedSet<String> sortedSet = new TreeSet<>(Comparator.comparingInt(String::length)
.thenComparing(Function.identity()));
sortedSet.addAll(fruits);
System.out.println(sortedSet); //[pear, apple, grapes, orange]
We create a Sorted Set to order the fruits from the shortest to the longest in terms of length. If there are two fruits with the same length, we order them lexicographically.
Let us create a PriorityQueue passing this sorted set. The created priority queue will use the same ordering.
PriorityQueue<String> fruitsQueue = new PriorityQueue<>(sortedSet);
//Ordered as
//pear -> apple -> grapes -> orange
Creating a PriorityQueue from a PriorityQueue
There is a constructor which accepts a PriorityQueue. The constructed priority queue will follow the same ordering as the given Priority Queue.
PriorityQueue<String> clonedFruitsQueue = new PriorityQueue<>(fruitsQueue);
Passing an initial capacity for the priority queue
As I said earlier, a priority queue is unbounded. It uses an array whose capacity grows when needed (it will create a new bigger array). But if we know the number of elements we will have in the queue (max) at a time, we can pass the capacity as an argument when constructing the queue. However, this is not a bound on the size of the queue. The queue can grow beyond this size. It is an optimization to avoid new array allocations and copying when the queue created with the initial default size (which is 11) is lesser than what we expect the queue size to be.
The below creates a priority queue with an initial size of 100.
PriorityQueue<String> priorityQueue = new PriorityQueue<>(100);
We can pass a comparator along with the capacity too.
PriorityQueue<String> priorityQueue = new PriorityQueue<>(100,
Comparator.comparing(String::length));
Iterator and toArray methods do not obey the queue ordering
The iterator method returns an Iterator that we can use to iterate over the elements of the queue. But it does not guarantee to traverse the elements of the priority queue in any particular order.
The same is true for the toArray method - the elements returned is not guaranteed to follow the ordering maintained within the queue.
List<String> fruits = List.of("apple", "orange", "pear", "grapes");
PriorityQueue<String> fruitsQueue = new PriorityQueue<>(fruits);
//toArray
System.out.println(Arrays.toString(fruitsQueue.toArray()));
System.out.println(Arrays.toString(fruitsQueue.toArray(new String[0])));
//Iterator
Iterator<String> iterator = fruitsQueue.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
When I ran this, the elements returned by toArray were in the following order.
[apple, grapes, pear, orange]
The Iterator too returned the elements in the same (above) order.
But within the queue, the ordering is different. It is
apple -> grapes -> orange -> pear
which can be confirmed by dequeuing the queue till it is empty.
while (!fruitsQueue.isEmpty()) {
System.out.println(fruitsQueue.remove());
}
Note that even though the toArray and the iterator returned the elements in this order, it does not guarantee that it won’t change in the future.
Time complexity of the Priority Queue methods
- Enqueuing and dequeuing methods i.e., add, remove, offer and poll - O(log(n))
- Retrieval methods i.e., peek, element and size - O(1)
A Practical Application Example for Priority Based Processing
Before I end this post, I would like to show an example that reflects real life application of the priority queue.
We have a Job or a Task which has a name, a priority and has the estimated time it takes to complete. We have provided a natural ordering by comparing the priority and breaking ties by the time it takes to complete (processingTime). In other words, the lower the priority number, the more important it is. If two jobs have the same priority, the one with lower processingTime will be more important. (See the #compareTo implementation below).
public class Job implements Comparable<Job> {
private final String name;
private final int priority;
private final int processingTimeInSeconds;
public Job(String name, int priority, int processingTimeInSeconds) {
this.name = name;
this.priority = priority;
this.processingTimeInSeconds = processingTimeInSeconds;
}
public int getPriority() {
return priority;
}
public int getProcessingTimeInSeconds() {
return processingTimeInSeconds;
}
@Override
public int compareTo(Job o) {
int priorityComparisonResult = Integer.compare(priority, o.priority);
return priorityComparisonResult != 0 ?
priorityComparisonResult
: Integer.compare(processingTimeInSeconds, o.processingTimeInSeconds);
}
@Override
public String toString() {
return name;
}
}
We define a JobQueue as having a queue of jobs. It has a method to add a new job and to get the next high priority job to be processed from the queue. The jobs are queued by using a priority queue (using the Job’s natural ordering).
public class JobQueue {
private final PriorityQueue<Job> jobs;
public JobQueue() {
jobs = new PriorityQueue<>();
}
public boolean addJob(Job job) {
return jobs.add(job);
}
public Optional<Job> getNextPriorityJob() {
return Optional.ofNullable(jobs.poll());
}
}
In our application, the getNextPriorityJob() can be called any number of times i.e., even when the queue is empty. Hence, I have used the poll() method and not the element() method since the latter will throw an exception if the queue is empty when we attempt to remove the head of it.
JobQueue Demo
We will create jobs, add it to the queue and retrieve jobs from it based on priority.
JobQueue jobQueue = new JobQueue();
jobQueue.addJob(new Job("job-1", 5, 10));
jobQueue.addJob(new Job("job-2", 1, 20));
jobQueue.addJob(new Job("job-3", 1, 30));
jobQueue.addJob(new Job("job-4", 1, 30));
System.out.println(jobQueue.getNextPriorityJob()); //Optional[job-2]
jobQueue.getNextPriorityJob().ifPresent(System.out::println); //job-4 / 3
jobQueue.getNextPriorityJob().ifPresent(System.out::println); //job-3 / 4
We added four jobs to the queue. There are three jobs tied at prio-1;but ties will be broken by the processing time. Hence, we get job-2 first. But there are two jobs with same priority and same processing time (jobs 3 and 4). They will be ordered arbitrarily. Hence job-2 can be followed by job-3 and job-4 or by job-4 and job-3.
After this, the queue has only one job in it (job-1) with priority 5. Let us add a new job with priority 4 to the queue.
jobQueue.addJob(new Job("job-5", 4, 100));
jobQueue.getNextPriorityJob().ifPresent(System.out::println); //job-5
jobQueue.getNextPriorityJob().ifPresent(System.out::println); //job-1
Since the newly added job has a high priority than job-1, it is added to the head of the queue. Hence, we get job-5 before job-1.
Processing by a Custom Comparator
If we wanted more flexibility to order the elements, we can add a constructor to the JobQueue class that accepts a custom comparator based on which it will order the jobs.
public JobQueue(Comparator<? super Job> comparator) {
jobs = new PriorityQueue<>(comparator);
}
Now we will switch the jobs ordering i.e., we will process the jobs with shortest processing time first, breaking ties by the priority.
JobQueue jobQueue = new JobQueue(Comparator.comparingInt(Job::getProcessingTimeInSeconds)
.thenComparing(Job::getPriority));
jobQueue.addJob(new Job("job-1", 5, 10));
jobQueue.addJob(new Job("job-2", 1, 20));
jobQueue.addJob(new Job("job-3", 1, 30));
jobQueue.addJob(new Job("job-4", 1, 30));
System.out.println(jobQueue.getNextPriorityJob()); //Optional[job-1]
jobQueue.getNextPriorityJob().ifPresent(System.out::println); //job-2
jobQueue.getNextPriorityJob().ifPresent(System.out::println); //job-3 / 3
jobQueue.getNextPriorityJob().ifPresent(System.out::println); //job-4 / 3
Job-1 has the lowest processing time and hence it is at the head of the priority queue followed by job-2. Jobs 3 and 4 can be ordered in any way since they have the same processing time and priority.
Conclusion
We learnt about the operations available on Queues and learnt that a Priority Queue in Java orders the elements by a certain order. This can either by the natural ordering of the objects or by a comparator passed during the queue creation time. We then looked at other constructor overloads available in the Priority Queue and leant that the toArray and iterator methods do not obey the internal queue ordering. Finally, we looked at the runtime complexities of the priority queue methods and saw a sample application using a priority queue.