Java Priority Queue

Introduction to Java Priority Queue

Java priority queue is a data structure that stores elements in a specific order based on their priority. It allows accessing the highest-priority element in the queue efficiently.

The priority queue utilizes a heap data structure to organize its elements. This indicates that the elements within the priority queue are arranged based on a comparator, which can be as basic as a regular number comparator.

Below is the hierarchy order of Priority Queue in Java.

A priority queue’s elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a comparator. In either case, the ordering of the elements represents their relative priority.

Declaration

where E is the type of elements held in this queue.

The class implements interfaces such as Serializable, Iterable<E>, Collection<E>, Queue<E>.

Important Points on Priority Queue

Here are a few important points on priority queue:

• It does permit a null value.
• A priority queue can’t be created for objects that are non-comparable based on any logic.
• Priority Queue is an unbound queue in Java as it has no fixed capacity, meaning it can grow dynamically as new elements are added to it.
• The least element with respect to ordering is known as the head of the queue.
• The PriorityQueue class in Java is not thread-safe by default.
• However, the PriorityBlockingQueue class can be used for thread-safe implementation of priority queue as it provides thread-safety and blocking operations for concurrent access.
• For methods like add and poll, O(log(n)) time is needed.

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Java Priority Queue Constructors

Here are the following constructors in the Java priority queue:

PriorityQueue()

It creates a priority queue that has a default capacity of 11.

PriorityQueue(Collection<E> c)

This PriorityQueue constructor with a collection as argument creates a priority queue containing all the elements in the specified collection.

PriorityQueue(int initialCapacity)

It creates a priority queue that has the specified initial capacity.

PriorityQueue(int initialCapacity, Comparator<E> comparator)

It creates a priority queue that has a specified initial capacity, and the order of elements is according to the specified comparator.

PriorityQueue(PriorityQueue<E> pq)

It creates a priority queue having elements that are present in the specified priority queue given as argument.

PriorityQueue(SortedSet<E> s)

It creates a priority queue having elements that are present in the specified SortedSet as argument.

Java Priority Queue Examples

Output:

Explanation: In this example, basic operations are performed like adding the elements, iterating through the elements, removing the elements from the Priority queue, etc.

Custom Comparator in Priority Queue

In the examples above, the elements in the priority queue are retrieved according to the natural order. However, this ordering can be customized. For this, we will create our own comparator class as shown below.

Example:

Output:

Explanation:

• In this example, we have created a priority queue by passing CustomComparator as an argument. This class implements the Comparator interface.
• When the compare() method is overridden, it makes the head of the element as the largest number. It implies reverse ordering is in place.
• The method compareTo() is used for comparing the two values.
• Finally, we have printed the elements of the priority queue nums to show the order of elements inside it.

Priority Queue with Java Objects

In real-life applications, priority queues are generally used with java objects. In order to understand this more clearly, let’s take an example.

Output:

Explanation:

• In this example, the CustomerOrder class stores the order of customers. It implements the Comparable interface which decides on what basis the object should be ordered in the priority queue.
• The ordering is decided by the function compareTo() in which the line o.orderId > this.orderId ? 1 : -1 instructs the compiler that the order should be sorted on basis of orderId in the descending order.
• Thus the objects c1, c2 and c3 are stored on the basis of their orderId in decreasing order as you can see in the output.

Time Complexity of Major Priority Queue Operations

Methods in Java Priority Queue

Applications of Priority Queue

Here are a few applications of priority queue

• Dijkstra's shortest path algorithm: Priority queue is used to implement Dijkstra's algorithm to find the shortest path between two nodes in a graph.
• Huffman coding: A priority queue can be used to implement Huffman coding, which is used for data compression.
• Job scheduling: Jobs can be prioritized based on their importance and scheduled accordingly using a priority queue.
• Event-driven simulations: Priority queue can be used to simulate events in a certain order of their priority.