Priority Queue in Java

Queue 

is a collection designed for holding elements prior to processing.

PriorityQueue

is an unbounded queue based on a priority heap and the elements of the priority queue are ordered by natural ordering. We can provide a Comparator for ordering at the time of instantiation of the priority queue.

A priority queue does not permit null elements.

A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException)

Priority Queue in Java

The PriorityQueue has following Constructors

  • public PriorityQueue() Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
  • public PriorityQueue(int initialCapacity) Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering. Parameters: initialCapacity - the initial capacity for this priority queue Throws: IllegalArgumentException - if initialCapacity is less than 1
  • public PriorityQueue(int initialCapacity, Comparator comparator) Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
  • public PriorityQueue(Collection c) Creates a PriorityQueue containing the elements in the specified collection. If the specified collection is an instance of a SortedSet or is another PriorityQueue, this priority queue will be ordered according to the same ordering. Otherwise, this priority queue will be ordered according to the natural ordering of its elements. Parameters: c - the collection whose elements are to be placed into this priority queue
  • public PriorityQueue(PriorityQueue c) Creates a PriorityQueue containing the elements in the specified priority queue. This priority queue will be ordered according to the same ordering as the given priority queue. Parameters: c - the priority queue whose elements are to be placed into this priority queue
  • public PriorityQueue(SortedSet c) Creates a PriorityQueue containing the elements in the specified sorted set. This priority queue will be ordered according to the same ordering as the given sorted set. Parameters: c - the sorted set whose elements are to be placed into this priority queue

PriorityQueue Features

  • It is an unbounded queue and grows dynamically. The default initial capacity is '11' which can be overridden using the initialCapacity parameter.
  • It does not allow NULL objects and Objects added to PriorityQueue MUST be comparable.
  • The objects of the priority queue are ordered by default in the natural order.
  • A Comparator can be used for custom ordering of objects in the queue.
  • The head of the priority queue is the least element based on the natural ordering or comparator based ordering. While polling the queue, it returns the head object.
  • If multiple objects are present of the same priority it can poll any one of them randomly.
  • PriorityQueue is not thread-safe. For the thread safety we need to use the PriorityBlockingQueue.

Method Detail

  • public boolean add(E e) Inserts the specified element into this priority queue.
  • public boolean offer(E e) Inserts the specified element into this priority queue.
  • public E peek() Description copied from interface: Queue Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
  • public boolean remove(Object o) Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element e such that o.equals(e), if this queue contains one or more such elements. Returns true if and only if this queue contained the specified element (or equivalently, if this queue changed as a result of the call).
  • public boolean contains(Object o) Returns true if this queue contains the specified element. More formally, returns true if and only if this queue contains at least one element e such that o.equals(e).
  • public Object[] toArray() Returns an array containing all of the elements in this queue. The elements are in no particular order. The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array. This method acts as a bridge between array-based and collection-based APIs.
  • public T[] toArray(T[] a) Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array. The returned array elements are in no particular order. If the queue fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this queue. If the queue fits in the specified array with room to spare (i.e., the array has more elements than the queue), the element in the array immediately following the end of the collection is set to null. Like the toArray() method, this method acts as a bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs. Suppose x is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of String: String[] y = x.toArray(new String[0]); Note that toArray(new Object[0]) is identical in function to toArray().
  • public Iterator iterator() Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order. Specified by: iterator in interface Iterable Specified by: iterator in interface Collection Specified by: iterator in class AbstractCollection
  • public int size() Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements returns Integer.MAX_VALUE. Specified by: size in interface Collection Specified by: size in class AbstractCollection
  • public void clear() Removes all of the elements from this priority queue. The queue will be empty after this call returns.
  • public E poll() Description copied from interface: Queue Retrieves and removes the head of this queue, or returns null if this queue is empty.
  • public Comparator comparator() Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements.

Example of java PriorityQueue

For natural ordering as well as with Comparator.

How to use priority queue in java?

We have a class Student that doesn’t provide any type of order, We use it with PriorityQueue. We have provided a comparator object to it.

Student.java 
 
 class Student {
	
	private int roll;
	private String name;
	
	public Student(int roll, String name){
		this.roll=roll;
		this.name=name;
	}

	public int getRoll() {
		return roll;
	}

	public String getName() {
		return name;
	}
	
}

StudentPriorityQueue.java 

 
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class StudentPriorityQueue {

	public static void main(String[] args) {
		
		/* natural ordering */
		Queue &ltInteger &gt integerPriorityQueue = new PriorityQueue &lt &gt(7);
		Random rand = new Random();
		for(int i=0;i <7;i++){
			integerPriorityQueue.add(new Integer(rand.nextInt(100)));
		}
			System.out.println("StudentPriorityQueue with natural ordering :");
				System.out.println();
		for(int i=0;i <7;i++){
			Integer in = integerPriorityQueue.poll();
			System.out.println("Roll Number :"+in);
		}
			System.out.println();
		/* PriorityQueue with Comparator */
		Queue &ltStudent &gt studentPriorityQueue = new PriorityQueue &lt &gt(7, idComparator);
		addDataToQueue(studentPriorityQueue);
		System.out.println("StudentPriorityQueue with with Comparator :");
		System.out.println();
		pollDataFromQueue(studentPriorityQueue);
		
	}
	
	/* Comparator anonymous class  */
	public static Comparator &ltStudent &gt idComparator = new Comparator &ltStudent &gt(){
		
		@Override
		public int compare(Student s1, Student s2) {
            return (int) (s1.getRoll() - s2.getRoll());
        }
	};

 
	private static void addDataToQueue(Queue &ltStudent &gt studentPriorityQueue) {
		Random rand = new Random();
		for(int i=0; i <7; i++){
			int roll = rand.nextInt(100);
			studentPriorityQueue.add(new Student(roll, "Anna"+roll));
		}
	}
	
	//utility method to poll data from queue
	private static void pollDataFromQueue(Queue &ltStudent &gt studentPriorityQueue) {
		while(true){
			Student student = studentPriorityQueue.poll();
			if(student == null) break;
			System.out.println("Student with Roll Number : "+student.getRoll() +" and Name : "+student.getName());
		}
	}

}

  

 
output:
StudentPriorityQueue with natural ordering :

Roll Number :14
Roll Number :31
Roll Number :41
Roll Number :46
Roll Number :59
Roll Number :62
Roll Number :94

StudentPriorityQueue with with Comparator :

Student with Roll Number : 2 and Name : Anna2
Student with Roll Number : 7 and Name : Anna7
Student with Roll Number : 39 and Name : Anna39
Student with Roll Number : 53 and Name : Anna53
Student with Roll Number : 54 and Name : Anna54
Student with Roll Number : 65 and Name : Anna65
Student with Roll Number : 73 and Name : Anna73

Questions covered

How to iterate through priority queue java?
How to use priority queue in java?

That's it. In this article, we have seen the Priority Queue in Java with an example. All source code in the article can be found in the GitHub repository.