What is the Java PriorityQueue?

The PriorityQueue is one of the important Java APIs built on the unbounded priority queue and priority heap. This article gets into some intricate information about this API and its use with appropriate code examples.

Overview

The PriorityQueue class is a part of the java.util package and is a generic implementation of a priority-based queue in Java. A queue is basically a data structure that defines specific norms to the process of insertion and retrieval of items from a store. The idea is quite similar to a number of people standing in a queue for say, getting a ticket. The first person standing in the queue gets the first chance to get the ticket and the last person gets one’s chance at the end. People get added to the end of the queue or from the tail end. Adding an item to the queue is technically called the process of enqueue, and the item removed from the queue is from the first in the line. This is called dequeue. The idea is to order the elements in a FIFO (first-in-first-out) manner.

Now, this is the simplest architecture and closely defines what a queue actually means and how it is to be simulated in a computer. A store is usually represented by a simple array where the storage and retrieval processes have this defined norm. The priority queue imposes some special norms above that. We shall see more of it down the line.

Java Implementation of the Queue

The Java API has an generic interface name, Queue<E>, in the java.util package. This is part of the Java Collection Framework APIs, designed to hold elements prior to processing. Being part of the Collection, it has all the basic Collection operations. The operations specific to its identity deals with insertion, extraction, and inspection of elements stored in it. Each of these operations has two distinct forms, such as one that throws an exception if operation fails and another that returns a special value, such as null or false, depending upon the operation. Note that, unlike typical queues, the concrete implementation of the Java Queue does not necessarily order elements in a FIFO manner. This is particularly true for priority-based queues where the ordering of elements is done according to the supplied comparator or natural ordering. But whatever be the ordering, the remove() or poll() method will always retrieve the element at the head of the queue. The specific difference between these two unlikely methods seemed to be a similar method is that one throws an exception (NoSuchElementException) on failure, and the later returns (null), a special value.

Note that the Queue<E> interface is not suitable to be used in concurrent programming because it does not define blocking queue methods where the enqueue and dequeue process waits for elements to appear in the queue or size to be available, for that matter. There is a specific interface, called BlockingQueue<E>, that extends the Queue<E> interface and addresses these issues.

There is an abstract class, called AbstractQueue<E>, which provides partial implementation of some of the queue operations. The PriorityQueue<E> class is a direct extension of this abstract class.

The Priority Queues

The Java implementation of the priority queue is a special type of queue where the ordering of the elements is determined either by its natural ordering principle or customized according to the Comparator supplied  during creation. The constructor we invoke during construction decides the ordering principle to be used with priority queue. Unlike the Queue<E>, which does not allow null elements, but some implements—such as LinkedList—do not prohibit insertion of null elements, either. PriorityQueue<E>, however, does not allow null elements at all. If the priority queue is constructed according to the natural ordering, any non-comparable element insertion would throw ClassCastException.

It is stated to be unbounded and based on the priority heap. Although the size of the queue is termed as unbounded, there is an internal capacity to determine the size of the array. This size grows automatically as elements are inserted. However, the details of the principle on which size increases is not specified.

There are seven types of overloaded constructors by which we can set the argument to specify the initial capacity of the queue, supply Comparator to specify custom ordering of elements, or accept everything as default with a no-argument constructor.

• PriorityQueue()
• PriorityQueue(int initialCapacity)
• PriorityQueue(int initialCapacity, Comparator<? Super E> comparator)
• PriorityQueue(Commection<? extends E> c)
• PriorityQueue(Comparator<? Super E> comparator)
• PriorityQueue(PriorityQueue<? extends E> c)
• PriorityQueue(SortedSet<? extends E> c)

Similar to Queue<E>, PriorityQueue<E> is also not synchronized and hence should be used cautiously in concurrent programming. However, there is a synchronized alternative to it, called PriorityBlockingQueue<E>. This works in the same way as PriorityQueue<E>, only with an additional qualification of being thread-safe.

The operations defined in PriorityQueue<E> are same as Queue<E>, with a few additions.

Quick Example #1

Let us implement some of the operations of PriorityQueue<E> with a simple program.

package org.mano.examples;
import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;
public class Example1 {
   public static void main(String[] args){
      PriorityQueue<String> pq = new PriorityQueue<>();
      pq.add("Mercury");
      pq.add("Venus");
      pq.add("Earth");
      pq.add("Mars");
      pq.add("Jupiter");
      pq.add("Saturn");
      // Get the most priority element based upon
      // natural alphabetic ordering in string
      System.out.println("Priority element "+pq.peek());
      // Queue elements
      show(pq);
      // Remove top of the queue element
      pq.poll();
      show(pq);
      // Retrieves element from the head of the queue
      pq.remove("Earth");
      show(pq);
      String result = pq.contains("Earth")?
         "Found Earth":"Earth Missing!";
      System.out.println(result);
      Object[] arr = pq.toArray();
      Arrays.sort(arr);
      System.out.println("");
      for (int i = 0; i<arr.length; i++)
         System.out.print(arr[i].toString()+"::");
   }
   public static void show(PriorityQueue<String> pq){
      Iterator<String> itr = pq.iterator();
      while (itr.hasNext())
         System.out.print(itr.next()+"::");
         System.out.println("");
   }
}

Output

Priority element Earth
Earth::Jupiter::Mercury::Venus::Mars::Saturn::
Jupiter::Mars::Mercury::Venus::Saturn::
Jupiter::Mars::Mercury::Venus::Saturn::
Earth Missing!

Jupiter::Mars::Mercury::Saturn::Venus::

Quick Example #2

Here is another quick example with a custom comparator.

package org.mano.examples;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Planet implements Comparable<Planet>{
   private String name;
   private double orbitPeriodInDays;
   public Planet(String name, double orbitPeriodInDays) {
      this.name = name;
      this.orbitPeriodInDays = orbitPeriodInDays;
   }
   public String getName() {
      return name;
   }
   public void setName(String name) {
      this.name = name;
   }
   public double getOrbitPeriodInDays() {
      return orbitPeriodInDays;
   }
   public void setOrbitPeriodInDays(double orbitPeriodInDays) {
      this.orbitPeriodInDays = orbitPeriodInDays;
   }
   @Override
   public int compareTo(Planet o) {
      return 0;
   }
   @Override
   public String toString() {
      return "Planet{" +
         "name='" + name + ''' +
         ", orbitPeriodInDays=" + orbitPeriodInDays +
         '}';
   }
   public static void main(String[] args){
      Comparator<Planet> nameSorter =
         Comparator.comparing(Planet::getName);
      PriorityQueue<Planet> priorityQueue = new
         PriorityQueue<>(nameSorter);
      priorityQueue.add(new Planet("Mercury",88));
      priorityQueue.add(new Planet("Venus",225));
      priorityQueue.add(new Planet("Earth",365.24));
      priorityQueue.add(new Planet("Mars",693.5));
      priorityQueue.add(new Planet("Jupiter",4343.5));
      priorityQueue.add(new Planet("Saturn",10767.5));
      priorityQueue.add(new Planet("Uranus",30660));
      priorityQueue.add(new Planet("Neptune",60152));
      Object[] list = priorityQueue.toArray();
      for (Object o: list)
         System.out.println(o);
   }
}

Output

Planet{name='Earth', orbitPeriodInDays=365.24}
Planet{name='Jupiter', orbitPeriodInDays=4343.5}
Planet{name='Mercury', orbitPeriodInDays=88.0}
Planet{name='Neptune', orbitPeriodInDays=60152.0}
Planet{name='Mars', orbitPeriodInDays=693.5}
Planet{name='Saturn', orbitPeriodInDays=10767.5}
Planet{name='Uranus', orbitPeriodInDays=30660.0}
Planet{name='Venus', orbitPeriodInDays=225.0}

Conclusion

The additional norm of the priority queue is that the item removed from the list is of the highest priority. The way Java imposes the priority rule to the otherwise normal queue is by attaching an ordering principle of the elements. This order can be customized as per the requirement of the programmer or set to remain default as well. That’s the essence of the priority queue implementation in Java.