Java PriorityQueue

PriorityQueue is a part of collection framework and is present in java.util package. Java PriorityQueue was introduced in java 1.5. Java PriorityQueue is implementation of Queue interface.

The java.util.PriorityQueue class is an unbounded priority queue based on priority heap. The elements of the priority queue are ordered according to their Comparable natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

PriorityQueue is a generic class that has this declaration:

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable

Here, E specifies the type of objects that the queue will hold.

• Java PriorityQueue inherits AbstractQueue class.
• Java PriorityQueue does not permit null elements.
• Java PriorityQueue can not be used for primitive types, like int, char, etc. We need to use wrapper classes.
• Java PriorityQueue is not synchronized.
• Java PriorityQueue is not thread-safe. You can make thread-safe by using java.util.concurrent.PriorityBlockingQueue class.
• Java PriorityQueue implementation provides O(log(n)) time for the enqueuing and dequeuing methods offer, poll, remove() and add
• Java PriorityQueue implementation provides linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods peek, element, and size.
• The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
• The order of iteration is undefined in PriorityQueue. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Java PriorityQueue constructors

There are seven constructors in Java PriorityQueue.

Constructor	Description
public PriorityQueue()	Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their Comparable natural ordering.
public PriorityQueue(int initialCapacity)	Creates a PriorityQueue with the specified initial capacity that orders its elements according to their Comparable natural ordering. It will throw IllegalArgumentException if initialCapacity is less than 1.
public PriorityQueue(Comparator<? super E> comparator)	Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator. This constructor was added in java 1.8.
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)	Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
public PriorityQueue(Collection<? extends E> 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 Comparable natural ordering of its elements.
public PriorityQueue(PriorityQueue<? extends E> 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.
public PriorityQueue(SortedSet<? extends E> 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.

Below is a simple code snippet showing Java PriorityQueue constructors.

//default PriorityQueue constructor
PriorityQueue<Integer> numbers = new PriorityQueue<Integer>();
numbers.add(10);
numbers.add(23);
numbers.add(30);

//priority queue with initial capacity
PriorityQueue<String> words = new PriorityQueue<String>(2000);

class MyComparator implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
    return o1 - o2;
    }
}

//priority queue with comparator
PriorityQueue<String> dictionary = new PriorityQueue<String>(new MyComparator());


//priority queue with default capacity and comparator
PriorityQueue<String> names = new PriorityQueue<String>(200, new MyComparator());

List<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");

//priority queue based on collection
PriorityQueue<String> queue = new PriorityQueue<String>(list);


//priority queue based on existing prioriy queue
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(numbers);


TreeSet<String> phoneNames = new TreeSet<String>();

// Priority queue based on sorted set
PriorityQueue<String> sortedQueue = new PriorityQueue<String>(phoneNames);

Java PriorityQueue methods

Method	Description
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()	Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
public boolean remove(Object obj)	Removes a single instance of the specified element from this queue, if it is present.
public boolean contains(Object obj)	Returns true if this queue contains the specified element.
public Object[] toArray()	Returns an array containing all of the elements in this queue. The elements are in no particular order.
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.
public Iterator<E> iterator()	Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.
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.
public void clear()	Removes all of the elements from this priority queue. The queue will be empty after this call returns.
public E poll()	Retrieves and removes the head of this queue, or returns null if this queue is empty.
public Comparator<? super E> comparator()	Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the Comparable natural ordering of its elements.
public Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this queue. This was introduced in Java 8.

Java PriorityQueue Example

The head of the priority queue is the least element based on natural ordering or comparator based ordering. If there are multiple objects with same ordering, then it can poll any one of them randomly. When we poll the queue, it returns the head object from the queue.

Java PriorityQueue common operations

Here we will see an example of commonly used method of PriorityQueue.

package com.walking.techie;

import java.util.PriorityQueue;

public class PriorityQueueDemo {


    public static void main(String[] args) {

        //default PriorityQueue constructor
        PriorityQueue<Integer> numbers = new PriorityQueue<Integer>();

        //add element to the priority queue
        numbers.add(40);
        numbers.add(10);
        numbers.add(23);
        numbers.add(30);

        //offer and add method are same
        numbers.offer(25);

        //peek method retrieves the head element, but does not remove
        System.out.println("Head element of the priority queue: "
                + numbers.peek());

        //remove method removes the specified object
        //it returns true if element removed from it.
        System.out.println("Element 50 removed from priority queue? "
                               + numbers.remove(new Integer(50)));

        numbers.add(50);
        System.out.println("Element 50 removed from priority queue? "
                               + numbers.remove(new Integer(50)));

        //This will retrieves and removes the head element of the priority queue,
        System.out.println(numbers.poll());
        System.out.println(numbers.poll());
        System.out.println(numbers.poll());
        System.out.println(numbers.poll());
        System.out.println(numbers.poll());
    }
}

Output of above program is shown below:

Head element of the priority queue: 10
Element 50 removed from priority queue? false
Element 50 removed from priority queue? true
10
23
25
30
40

Java PriorityQueue Iterator

Java PriorityQueue iterator is fail-fast, so iterator will throw java.util.ConcurrentModificationException if the queue is modified at any time after the iterator is created, in any way except through the iterator's own remove method. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

The iterator of PriorityQueue does not return the elements in any particular order.

package com.walking.techie;

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

public class PriorityQueueIteratorDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> numbers = new PriorityQueue<Integer>();
        numbers.add(23);
        numbers.add(34);
        numbers.add(13);
        numbers.add(2);
        numbers.add(28);
        System.out.print("Elements of numbers queue [");

        // traversal over priority queue using iterator
        Iterator<Integer> iterator = numbers.iterator();
        while (iterator.hasNext()) {
            int number = iterator.next();
            System.out.print(number + " ");
        }
        System.out.println("]");

        // ConcurrentModificationException
        iterator = numbers.iterator();
        while (iterator.hasNext()) {
            int number = iterator.next();
            System.out.print(number + " ");
            if (number == 28) {
                System.out.println();
                numbers.add(12); // throw ConcurrentModificationException
            }
        }
    }
}

Output of above program is shown below:

Elements of numbers queue [2 13 23 34 28 ]
2 13 23 34 28
Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.PriorityQueue$Itr.next(PriorityQueue.java:535)
 at com.walking.techie.PriorityQueueIteratorDemo.main(PriorityQueueIteratorDemo.java:27)

Java PriorityQueue Example with natural order and Comparator

Let's see an example of java PriorityQueue for natural ordering as well as with Comparator.

We have our Student class does not provide any type of sorting. so when we will use it with PriorityQueue we should provide a comparator object of it.

package com.walking.techie;

public class Student {
    private Integer rollNumber;
    private String name;

    public Student(Integer rollNumber, String name) {
        this.rollNumber = rollNumber;
        this.name = name;
    }

    public Integer getRollNumber() {
        return rollNumber;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[").append(" rollNumber = ").
                append(rollNumber).append(" name = ").
                append(name).append(" ]");
        return builder.toString();
    }
}

We will create an NameComparator class to provide sorting of Student instance based of name field. We also use java random number generation to generate random Interger and name of the student.

Here is the final test code to show PriorityQueue with natural order as well comparator.

package com.walking.techie;

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

public class PriorityQueueExample {

    public static void main(String[] args) {
        //priority queue example using natural order
        PriorityQueue<Integer> integerPriorityQueue = new
                PriorityQueue<Integer>(8);

        //add elements in priority queue
        Random rand = new Random();
        for (int i = 1; i <= 8; i++) {
            integerPriorityQueue.add(new
                    Integer(rand.nextInt(100)));
        }

        //display elements of the priority queue
        for (int i = 1; i <= 8; i++) {
            System.out.println("Element : " +
                    integerPriorityQueue.poll());
        }


        // priority queue example with comparator
        NameComparator nameComparator = new PriorityQueueExample()
                .new NameComparator();

        PriorityQueue<Student> students = new PriorityQueue
                <Student>(8, nameComparator);

        for (int i = 1; i <= 8; i++) {
            students.add(new Student(i, "student" + rand.nextInt(100)));
        }


        //poll student from priority queue

        for (int i = 1; i <= 8; i++) {
            System.out.println("Student: " + students.poll());
        }
    }


    public class NameComparator implements
            Comparator<Student> {

        @Override
        public int compare(Student o1, Student o2) {
            return o1.getName().compareTo(o2.getName());
        }
    }
}

Output of above program is shown below:

We have used java Random class to generate integer number, so will get diffrent output everytime. Output of the above example will look like below.

Element : 7
Element : 16
Element : 19
Element : 22
Element : 35
Element : 50
Element : 52
Element : 88
Student: [ rollNumber = 6 name = student12 ]
Student: [ rollNumber = 5 name = student13 ]
Student: [ rollNumber = 3 name = student32 ]
Student: [ rollNumber = 1 name = student37 ]
Student: [ rollNumber = 4 name = student45 ]
Student: [ rollNumber = 8 name = student68 ]
Student: [ rollNumber = 2 name = student7 ]
Student: [ rollNumber = 7 name = student87 ]

From above discussed all the example it’s clear that least element was at head and got polled first.

PriorityQueue<Student> students = new PriorityQueue<Student>(8);

If we won’t provide comparator while creating students instance of PriorityQueue, it will throw ClassCastException at runtime.

Exception in thread "main" java.lang.ClassCastException: com.walking.techie.Student cannot be cast to java.lang.Comparable
 at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:652)
 at java.util.PriorityQueue.siftUp(PriorityQueue.java:647)
 at java.util.PriorityQueue.offer(PriorityQueue.java:344)
 at java.util.PriorityQueue.add(PriorityQueue.java:321)
 at com.walking.techie.PriorityQueueExample.main(PriorityQueueExample.java:36)

Java PriorityQueue to Array Example

Here is example to convert a queue into Array and Array into queue. Sometimes we need to convert array into queue and vice-versa.

package com.walking.techie;

import java.util.Arrays;
import java.util.PriorityQueue;

public class PriorityQueueToArray {
    public static void main(String[] args) {
        PriorityQueue<String> phone = new PriorityQueue<>();
        phone.add("Nokia");
        phone.add("Samsung");
        phone.add("MI");
        phone.add("Zenfone");
        System.out.println("Elements of phone " + phone);

        // convert priority queue to Array
        String[] array1 = new String[phone.size()];
        phone.toArray(array1);
        System.out.println("Elements of Array1 " + Arrays.toString(array1));

        Object[] array2 = new Object[phone.size()];
        array2 = phone.toArray();
        System.out.println("Elements of Array2 " + Arrays.toString(array2));

        // convert array to queue
        PriorityQueue<String> queue = new PriorityQueue<>(Arrays.asList(array1));
        System.out.println("Elements of priority queue " + queue);
    }
}

Output of above program is shown below:

Elements of phone [MI, Samsung, Nokia, Zenfone]
Elements of Array1 [MI, Samsung, Nokia, Zenfone]
Elements of Array2 [MI, Samsung, Nokia, Zenfone]
Elements of priority queue [MI, Samsung, Nokia, Zenfone]

Java PriorityQueue to List Example

List and Queue both are different from each others, but sometimes we need List from Queue and vice-versa.

package com.walking.techie;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class PriorityQueueToList {
    public static void main(String[] args) {
        PriorityQueue<String> phone = new PriorityQueue<>();
        phone.add("Nokia");
        phone.add("Samsung");
        phone.add("MI");
        phone.add("Zenfone");
        System.out.println("Elements of phone " + phone);

        // convert queue to list
        List<String> phoneList = new ArrayList<String>(phone);
        System.out.println("Elements of phoneList " + phoneList);

        // convert list to priority queue
        PriorityQueue<String> phoneQueue = new PriorityQueue<String>(phoneList);
        System.out.println("Elements of priority queue " + phoneQueue);
    }
}

Output of above program is shown below:

Elements of phone [MI, Samsung, Nokia, Zenfone]
Elements of phoneList [MI, Samsung, Nokia, Zenfone]
Elements of priority queue [MI, Samsung, Nokia, Zenfone]

Java PriorityQueue removeIf

removeIf method was added in Java 8 and available in Collection interface.This method will remove all of the elements in the PriorityQueue which will satisfy the given prediacte. Below is the program of PriorityQueue removeIf example.

package com.walking.techie;

import java.util.PriorityQueue;
import java.util.function.Predicate;

public class PriorityQueueRemoveIf {
    public static void main(String[] args) {
        PriorityQueue<Integer> numbers = new PriorityQueue<Integer>();
        // add numbers from 1 to 10 in priorityQueue
        for (int i = 10; i >= 0; i--) {
            numbers.add(i);
        }

        Predicate<Integer> filter = new PriorityQueueRemoveIf().new EvenPredicate<Integer>();

        // priorityQueue before removeIf operation
        System.out.println("Numbers queue " + numbers);

        numbers.removeIf(filter);
        System.out.println("Numbers queue after removeIf call " + numbers);
    }

    private class EvenPredicate<T> implements Predicate<Integer> {

        @Override
        public boolean test(Integer t) {
            return t % 2 == 0;
        }
    }
}

Output of above program is shown below:

PriorityQueue is an unbounded queue based on a priority heap and the elements of the priority queue are ordered by default in natural order. So elements of priority queue is display like below.

Numbers queue [0, 1, 5, 4, 2, 9, 6, 10, 7, 8, 3]
Numbers queue after removeIf call [1, 3, 5, 7, 9]