How to use PriorityQueue in Java? An Example

PriorityQueue is another data structure from Java Collection framework, added in Java SE 5. This class implements Queue interface and provides a sorted element from the head of the queue. Though it provides sorting, it's little different with other Sorted collections e.g. TreeSet or TreeMap, which also allows you to iterate over all elements, in priority queue there is no guarantee on iteration. The only guaranteed PriorityQueue gives is that lowest or highest priority element will be on 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 highest/lowest priority element at the head of the queue.  priority queue data structure is internally implemented using 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, 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 highest or lowest priority element.

Good knowledge of Java Collection framework is absolutely necessary to become an expert Java developer and if you want to become one, I suggest you to read Java Generics and Collection by Maurice Naftalin. One of the best book which extensively cover 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, head of the queue is updated if a new value is less than or greater than head value.

By default, elements are sorted in increasing order and head contains the smallest elements. You can retrieve head of priority queue without removing it by using 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, Queue interface provides two sets of methods for similar task 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 other return special value 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 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.

PriorityQueue Example in Java

In this example, you will also learn how to iterate over all elements of PriorityQueue in Java. You can do that by using Iterator interface and actually its 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
        // 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");


size of PriorityQueue : 6
head of the PriorityQueue : 1
Current value of head : 2
size of PriorityQueue : 5
Iterating over PriorityQueue

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 Comparator interface and overriding compare() method. You can use PriorityQueue 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 notification at the top. Since you cannot store object, which is not comparable, its 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.

Java PriorityQueue Example

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 is in order of O(log(n))

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

11) PriorityQueue provides constant time performance for peek(), element() and size() method, which means you can retrieve a maximum or minimum element in constant time from 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 which implement Comparable or Comparator interface. If you are using Queue interface to access PriorityQueue object then I suggest you to use the method defined their instead of Collection interface method e.g. prefer offer() over add(),  peek() over element() and poll() over remove() method while working with priority queue in Java.

Recommended books for further learning Data structure and Collections in Java

  • Core Java Volume 1 9th Edition by Cay S. Horstmann (see here)
  • Data Structure and Algorithm in Java (see here)
  • Java Generics and Collections by Maurice Naftalin (see here)

No comments:

Post a Comment