Priority Queue in Java

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:

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.

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:

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.

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.

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’ order in the array may not be the same as 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. 

apple -> grapes -> orange -> pear

while (!fruitsQueue.isEmpty()) {
    System.out.println(fruitsQueue.remove());
}

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

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

jobQueue.addJob(new Job("job-5", 4, 100));

jobQueue.getNextPriorityJob().ifPresent(System.out::println); //job-5
jobQueue.getNextPriorityJob().ifPresent(System.out::println); //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.

Other Resources

• PriorityQueue Javadoc
• Priority Queue from java67
• Journaldev PriorityQueue