Priority Queue | Java

Introduction

A priority queue is a special queue where:

Every item in the queue has a priority, and
Higher-priority items are dequeued before lower-priority items.

A priority queue can be implemented using many of the data structures (an array, a linked list, or a binary search tree). However, those data structures do not provide the most efficient operations. To make all of the operations very efficient, Heap is used.

The binary heap is a data structure that can efficiently support the basic priority-queue operations. In a binary heap, the items are stored in an array such that each key is guaranteed to be larger than (or equal to) the keys at two other specific positions. In turn, each of those keys must be larger than two more keys, and so forth. When a priority queue is implemented using a heap, the worst-case times are :

To enqueue an item, add it to the heap using the priority as the key (O(lg(n)))
To peek at the highest priority item, look at the item at the top. (O(1))
To dequeue the highest priority item, remove the top item from the heap. (O(lg(n)))

When a priority queue is implemented using a heap, the worst-case times for both insert and remove are logarithmic in the number of values in the priority queue.

Priority queue in Java

PriorityQueue belongs to the Collections Framework. It is based on priority heap and it is an implementation of Queue interface. This data structure can be used when we need a Queue implementation and we have a requirement to maintain the elements of that collection in a specific sorted order based on each element’s 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. 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.

Example

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.

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.

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

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
        pq.add(3);
        pq.add(7);
        pq.add(2);
       
        // 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("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
       
        // Iterating over PriorityQueue, iterator returned
        // by PriorityQueue doesn't guarantee any order
        Iterator<Integer> itr = pq.iterator();
      
        while(itr.hasNext()){
            System.out.println(itr.next());
        }
    }
}

Key points

A Comparator can be provided in the constructor when instantiating a PriorityQueue. Then the order of the items in the Queue will be decided based on the Comparator provided. If a Comparator is not provided, then the natural order (Comparable) of the Collection will be used to order the elements.
null is not allowed in this Collection.
Head of the Queue is the least item in the order.
Ordering ties between the PriorityQueue elements are decided arbitrarily.
PriorityQueue is not synchronized. PriorityBlockingQueue is the thread-safe counterpart of PriorityQueue.
PriorityQueue is unbounded and it grows dynamically based on the number of elements in the Queue. It has internal capacity at any given time and it is increased as the elements are added. The policy for this internal capacity and increment is not specified or standardized.

Important Methods

add(E e)
Inserts the specified element into this priority queue.
contains(Object o)
Returns true if this queue contains the specified element.
Iterator<E> iterator()
Returns an iterator over the elements in this queue.
E peek()
Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E poll()
Retrieves and removes the head of this queue, or returns null if this queue is empty.
boolean remove(Object o)
Removes a single instance of the specified element from this queue, if it is present.
int size()
Returns the number of elements in this collection.
public boolean isEmpty()
Returns true if this collection contains no elements.
public boolean equals(Object obj)
Indicates whether some other object is “equal to” this one. For any non-null reference value x, x.equals(null) should return false.