PriorityQueue in Java? Example Tutorial

PriorityQueue is another data structure from the Java Collection framework, added in Java SE 5. This class implements the Queue interface and provides a sorted element from the head of the queue. Though it provides sorting, it's a little different from other Sorted collections e.g. TreeSet or TreeMap, which also allows you to iterate over all elements, in the priority queue, there is no guarantee on iteration. The only guaranteed PriorityQueue gives is that the lowest or highest priority element will be at the head of the queue. So when you call remove() or poll() method, you will get this element, and next on priority will acquire the head spot. Like other collection classes which provide sorting, PriorityQueue also uses Comparable and Comparator interface for priority.

When you add or remove elements from PriorityQueue, other elements are compared to each other to put the highest/lowest priority element at the head of the queue.  

priority queue data structure is internally implemented using a binary heap data structure, which allows constant time access to the maximum and minimum element in a heap by implementing max heap and min heap data structure.

In this data structure root of the binary tree always contain either maximum value (max heap) or minimum value (min heap), since you have constant time access to root, you can get max or minimum value in constant time. Once this element is removed from the root, the next maximum/minimum is promoted to root.

So, if you want to process elements in their relative priority order, you can use PriorityQueue in Java. It provides constant-time access to the highest or lowest priority element.

Good knowledge of the Java Collection framework is absolutely necessary to become an expert Java developer and if you want to become one, I suggest you read Java Generics and Collection by Maurice Naftalin. One of the best book which extensively covers this topic and explains about almost all the collection classes available in Java till Java SE 6.

Java PriorityQueue Example

Here is our sample program to demonstrate how to use PriorityQueue in Java. As I said you can use PriorityQueue to store objects which required processing in a certain order decided by their priority e.g. processing order with the highest value first or lowest value first. 

In this example, you will learn how to add elements into PriorityQueue, how to remove elements from PriorityQueue, how to poll, and how to peek elements from PriorityQueue in Java.

We first create a priority queue of integer values with a capacity of 16 elements. Then we add numbers using the add() method of the queue. Whenever you add a number, the head of the queue is updated if a new value is less than or greater than the head value.

By default, elements are sorted in increasing order and the head contains the smallest elements. You can retrieve the head of the priority queue without removing it by using the peek() method.

You can also use the poll() method of PriorityQueue to get head value but this will also remove the element from the queue. It is actually good if you are consuming elements instead of just viewing it.

If you remember, the Queue interface provides two sets of methods for similar tasks e.g. add() and offer() for adding elements, poll() and remove() for removing a head element from PriorityQueue and peek() and element() for retrieving the head of the queue without removing.

The difference between these two sets of the method is that one throws an exception if failed while the other return special values e.g. false or null if failed. This is also the reason why PriorityQueue doesn't allow adding null elements because then you cannot differentiate between the normal object and the special value.

You can also read  Core Java Volume 1 - Fundamentals by Cay S. Horstmann to learn more about PriorityQueue and how to use it correctly in your Java application.

In this example, you will also learn how to iterate over all elements of PriorityQueue in Java. You can do that by using the Iterator interface and actually it's the same as how to iterate over ArrayList in Java. Just remember that PriorityQueue doesn't keep all elements in some order, it only makes effort to keep the lowest priority of element at the head of the queue.

package dto;

import java.util.Iterator;
import java.util.PriorityQueue;

/**
 * Simple Java Program to demonstrate how to use PriorityQueue
 * in Java. PriorityQueue is used to process elements as
 * per their priority defined by Comparator or Comparable.
 *
 * @author Javin Paul
 */
public class PriorityQueueDemo {

    public static void main(String[] args) {

        // creating an instance of PriorityQueue in Java
        // Its better to define initial capacity because
        // its backed by array
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(16);
       
       
        // adding numbers into PriorityQueue in arbitrary order
        pq.add(3);
        pq.add(7);
        pq.add(2);
        pq.add(4);
        pq.add(1);
        pq.add(5);
       
        // Now, let's if PriorityQueue keeps the smallest
        // element in head or not. Let's use peek  method
        // to check that, peek() returns the head of the
        // queue
       
        Integer head = pq.peek();
        System.out.println("size of PriorityQueue : " + pq.size());
        System.out.println("head of the PriorityQueue : " + head); // 1
       
        // Now, let's remove the head and see what comes
        // next, you can use poll() method to remove
        // element from head
       
        head = pq.poll(); // 1
        head = pq.peek();
       
        System.out.println("Current value of head : " + head);
        System.out.println("size of PriorityQueue : " + pq.size());
   
       
        // Iterating over PriorityQueue, iterator returned
        // by PriorityQueue doesn't guarantee any order
        Iterator<Integer> itr = pq.iterator();
        System.out.println("Iterating over PriorityQueue");
       
        while(itr.hasNext()){
            System.out.println(itr.next());
        }
    }

}

Output
size of PriorityQueue : 6
head of the PriorityQueue : 1
Current value of head : 2
size of PriorityQueue : 5
Iterating over PriorityQueue
2
4
3
7
5

When to use PriorityQueue in Java?

Use when you want to process elements on some priority e.g. processing the highest priority element first or lowest priority element first. You can decide relative priority comparison by using the Comparator interface and overriding compare() method. 

You can use Priority Queue to process a job of highest priority first. If you are implementing a dashboard kind of interface, you can also use this class to bubble up important issues, alerts or notifications at the top. 

Since you cannot store objects, which are not comparable, it's useless for them. You also need to pay some price for keeping the head as per priority so if you are not required that feature better not to use this class.

Important points about PriorityQueue

1) PriorityQueue was added in JDK 1.5 and this class is written by Josh Bloch and Doug Lea.

2) PriorityQueue is based upon priority heap where elements are ordered on their priority, according to their natural order provided by Comparable or custom order provided by Comparator.

3) Any elements which you want to store in PriorityQueue must implement either Comparator or Comparable interface. Priority of elements are represented by implementing compare() or compareTo() method of respective interface.

4) You cannot store incompatible elements in PriorityQueue, which means you cannot store Integer and String on a PriorityQueue of Object, this will result in ClassCastException

5) PriorityQueue does not allow null elements, adding nulls will result in NullPointerException

6) If multiple elements are tied for least value then anyone of them can occupy the head of the queue, ties are broken arbitrarily.

7) PriorityQueue is unbounded, which means you can add as many elements as you want, but it's backed by an array and has an internal capacity to govern the size of an array.

8) Iterator returned by PriorityQueue doesn't guarantee any ordered traversal. If you need ordered traversal consider using Arrays.sort(pq.toArray());

9) The priority queue class is not synchronized, so you and not share between multiple threads if one of the threads modifies the queue.

10) Time complexity of enqueuing and dequeuing elements are in order of O(log(n))

11) Time complexity is liner for remove(object) and contains(object)

11) PriorityQueue provides constant-time performance for the peek(), element(), and size() method, which means you can retrieve a maximum or minimum element in constant time from the priority queue in Java.


That's all about how to use PriorityQueue in Java with an example. You have also learned some important things about PriorityQueue. Just remember that PriorityQueue in Java was added on JDK 1.5 and available in Java SE 6, 7, and 8 but not available in JDK 1.4. Also, similar to TreeSet or TreeMap you can only store elements that implement Comparable or Comparator interface. 

If you are using the Queue interface to access the PriorityQueue object then I suggest you to use the method defined there instead of the Collection interface method e.g. prefer offer() over add(),  peek() over element() and poll() over remove() method while working with priority queue in Java.

And, now one question for you? What is difference between priority queue and heap data structure?