Java Priority Queue: not a classical queue

In this article we learn a priority queue, Java class, that implements Queue interface. What does a programmer know of regular Queue Interface? First of all, this interface is based on the FIFO principle or “first in first out”. That reminds a regular queue in its common meaning. You want to get coffee from McDrive? If your car is the first near the window, you’ll get your coffee before the driver who is next.

Queue Interface declaration

public interface Queue<E> extends Collection<E>

What is a Priority Queue

What is a Priority Queue? First of all it is a class that implements the Queue interface in case of inserting an element from the back and removing an element from the head. However it is not a usual queue inside. The order of Java priority queue elements depends on the priority of the elements. The element with highest priority will be moved to the head of the queue. If you delete (serve) the highest ranked element, the second one goes to the head to get its coffee. How is priority determined? According to the documentation, 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. A priority queue based on a priority min heap. That means, in case of numbers queue elements, the first element of the queue will be the minimal of these numbers. Pretty often after reading this definition rookie students begin to think that priority queue is sorted in a linear sense. That is, if, say, we use a queue whose elements are natural numbers, then the first element will be the smallest, and the last - the largest. This is not entirely true. To understand how the priority queue actually works and what it gives, you need to figure out how the heap works. We consider the internal structure of the priority queue using an example a bit later. Now let’s dwell on its external attributes.

PriorityQueue class constructors and declaration

PriorityQueue class provides 6 different ways to construct a priority queue in Java.

• PriorityQueue() - empty queue with the default initial capacity (11) that orders its elements according to their natural ordering.
• PriorityQueue(Collection c) - empty queue containing the elements in the specified collection.
• PriorityQueue(int initialCapacity) - empty queue with the specified initial capacity that orders its elements according to their natural ordering.
• PriorityQueue(int initialCapacity, Comparator comparator) - empty queue with the specified initial capacity that orders its elements according to the specified comparator.
• PriorityQueue(PriorityQueue c) - empty queue containing the elements in the specified priority queue.
• PriorityQueue(SortedSet c) - empty queue containing the elements in the specified sorted set.

Priority Queue in Java is declared the next way:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

Creating PriorityQueue

Let’s create a priority queue of integers. Priority Queue implementation, Java code:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

We have created a priority queue without arguments. In this case, the head of the priority queue is the minimal number of the queue. If you remove the head, the next smallest element will take this place. So you can remove elements from the queue in ascending order. If necessary you can change the principle of ordering using Comparator interface.

Java PriorityQueue Methods

PriorityQueue Java class has important methods to add, remove and check elements.

Insert Elements into Priority Queue

• boolean add(object) inserts the specified element into priority queue. Returns true in case of success. If the queue is full, the method throws an exception.
• boolean offer(object) inserts the specified element into this priority queue. If the queue is full, the method returns false.

You may use both of the adding operations, there are no differences for majority cases. Here is a little example of initiation and adding elements into priority queue.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

The output is:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

The order of the elements seems to be weird, we’ll explain it later.

Retrieving and removing elements from the Priority Queue

• boolean remove(object) removes a single instance of the specified element from this queue, if it is present.
• Object poll() retrieves and removes the head of this queue. Returns null if the queue is empty.
• void clear() removes all elements from the priority queue.
• Object element() retrieves the head of this queue without removing it. Throws NoSuchElementException if the queue is empty.
• Object peek() retrieves the head of the queue without removing it. Returns null if the queue is empty.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

The output:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

As you may see, trying to print out the head of the empty Queue using element() method leads to NoSuchElementexception.

PriorityQueue Comparator

• Comparator comparator() returns the comparator that used to order the elements in the queue. Returns null if the queue is sorted according to the natural ordering of its elements.

Java priority queue, example with comparator

We used natural (ascending) order in the code examples above, but sometimes we should change it. Here is Java priority queue example, where we create our own internal comparator class that implements the Comparator interface. Our comparator will sort elements from the biggest to the smallest.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

The Output:

the head of Queue = 5
5
4
3
2
1

The head of Queue now is not the minimal, but maximal element, and the order was changed to reversed.

Iterating over PriorityQueue using iterator

ProrityQueue is a part of the Collection framework and implements the Iterable<> interface. To iterate over elements of a priority queue you can use the iterator() method. Here is an example:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

The output:

1 2 4 5 3 

More PriorityQueue methods

• boolean contains(Object o) returns true if the queue contains the o element.
• int size() returns the number of elements in this queue.
• Object[] toArray() returns an array containing all of the elements in this queue.

Here is an example:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

The output:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue Java 8 definition

If you open the priorityqueue java 8 documentation, you’ll find there the next definition: An unbounded priority queue based on a priority heap. 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. 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). Heap is a very important word here. It explains the properties of Priority Queue elements ordering.

The principle of PriorityQueue work: Binary Heap

Let’s start with an example. Let's create two objects implementing the Queue interface. One of them LinkedList, the second — PriorityQueue. Both of them have 5 elements of Integer (1,2,3,4 and 5) and we start to put the elements into our queues from the biggest to the smallest. So, the first comes 5, then 4, 3, 2 and the last one will be 1. Then print out both lists to check the order out.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

The result of these code working is the next:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Well, linkedlist order is predictable and understandable. It is ordered according to FIFO principle. We started with 5, so this element is the very first in line, then goes 4 and so on. What can we tell about priority queue order? Docs said that the elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time. However this order doesn’t seem to be “natural” in linear sorting meaning. We’d rather expect [1, 2, 3, 4, 5], not [1, 2, 4, 5, 3]. To understand why the order of retrieving is like it is, we should recall that priority queue based on a heap. What is the heap? It is a data structure based on binary tree. The main property of the heap: the priority of each parent is greater than the priorities of its children. Let me remind you that a tree is called a complete binary if each parent has no more than two children, and the filling of the levels goes from top to bottom (from the same level — from left to right). Binary heap reorganises itself each time elements are added or removed from it. In case of min-heap, the smallest element goes to the root regardless of the order of its insertion. Priority queue based on this min-heap. That means, in case of numbers queue elements, the first element of the queue will be the minimal of these numbers. If you delete the root, the next smallest becomes a root.

Let’s turn to our example.

Step 1. We put ‘5’ into the priority queue. It becomes a root. Step 2. We add ‘4’ into priority queue. 4 <5, so the new element should be higher than the older one. The 4 becomes a root, 5 is its left child. Now the data structure in Java is [4, 5] Step 3. We add ‘3’. Temporarily it becomes a right child of a root (4). However, 3 < 4, so we should lift it up. Exchange 3 and 4. Now we have a structure such as [3, 5, 4] Step 4. We add ‘2’. It becomes a left child of 5. 2<5, so exchange them. 2 becomes a left child of 3, 2 < 3, so one more exchange process. Now we have a structure [2,3,4,5] Step 5. We add ‘1’. It comes from the right child of the 3 to the left child of the 2, and then goes to the root. The result data structure: [1,2,4,5,3] The Removal process starts from a root, and it provokes the reverse procedures. So, first we have 1 as a root, then 2, 3, 4 and at last 5. That’s why using removing operation poll()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

we’ve got “sorted” in linear sence output:

1
2
3
4
5

So priority queue could be effective for some operations. It takes O(log N) time to insert and delete each element, and you can get the minimal element in O(1). Here is the full example:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

It is important to understand that priority queues are based on binary heaps, so they do not keep elements in linear sorted order. Every way from the root to the leaf is ordered, but different ways from the root are not. That means you can get the minimal element of the queue very quickly.

What you should know about priority queue. Brief list

• Priority Queue does not allow NULL objects.
• You can add only comparable objects into PriorityQueue.
• Priority queue is builded as a min heap, a kind of binary tree. The minimal element is a root. The objects of the priority queue are ordered by default in natural order.
• You can use Comparator if you need custom ordering.
• PriorityQueue is not thread safe, so you better use PriorityBlockingQueue to work in a concurrent environment.
• PriorityQueue provides O(log(n)) time for add and poll methods and O(1) to get minimal elements.