PriorityQueue in Java

A PriorityQueue in Java is a queue or collection of items in which elements are placed in order of their priority.

It is an abstract data type comparable to an ordinary queue except for its removal technique.

An ordinary queue is a first-in-first-out (FIFO) data structure. In FIFO, items are added to the end of the queue and deleted from the beginning.

But, In Java PriorityQueue, items are kept in order of their priority. When accessing elements, the element with the greatest priority is deleted first before the element with the lower priority.

PriorityQueue was introduced in Java 1.5 version and it is part of the Java Collection Framework. It is found in java.util. PriorityQueue package.

Let’s understand it using a live example.

Realtime Examples of PriorityQueue in Java

1. A common example of a priority queue is the work schedule. Works are added in random order yet each task has a priority. Urgent work is accorded the greatest priority and is done first.

2. In a hospital, the emergency department gives priority numbers to patients. The patient with the greatest priority gets checked up first.

Similarly, the Java PriorityQueue class offers an implementation of a priority queue. We may establish a queue with its own priority queue in java.

Priority is selected by Comparator supplied in the constructor PriorityQueue(initialCapacity, Comparator) when the priority queue is constructed.

If no comparator is given, PrirotyQueue organizes its items according to their natural ordering using the Comparable interface. In simple terms, by default, the priority is based on the natural order of the components.

For example, if all items of the type of Integer and no comparator is specified at the time of creation, natural ordering of elements is utilized to prioritize them.

The element at the head of the priority queue is the smallest element with regard to specified ordering. That is, the element holding the lowest value will be allocated with the greatest priority and removed first from the queue.

Look at the following image where a new element is added in the queue and PriortyQueue organizes its items according to the natural order.
The element with the biggest value will be allocated with the lowest priority and it will be kept at the tail of the queue.

Removal of components takes occurs from the front end of the queue. Look at the following figure to understand better.

If numerous items are deadlocked for the greatest priority, one of those elements is randomly picked as the least element. Similarly, when there is a tie among entries at the tail of the priority queue, it is likewise randomly picked.

Hierarchy of Java PriorityQueue

PriorityQueue extends AbstractQueue class to enable a priority-based queue. It implements the Queue interface, Serializable interface but does not implement Cloneable.

The hierarchical structure of PriorityQueue in java is illustrated in the following picture.

Features of PriorityQueue

There are some significant elements of Priority Queue that are as follows:

1. The basic data structure for developing PriorityQueue in Java is Binary Heap.

2. Java PriorityQueue doesn’t tolerate null elements.

3. It does not enable the insertion of non-comparable items when depending on natural ordering.

4. PriorityQueue is an implementation class for unbounded priority queue but it has an internal capacity that controls the size of an array used to hold priority queue components.

The capacity number is always at least as great as the queue size. As items are placed into the priority queue, their internal capacity expands automatically.

5. Element at the front of the priority queue is the least element.

6. Element at the tail of the priority queue is the largest element.

7. Removal of items always takes place from the front end (head) of the queue.

8. PriorityQueue is not synced. That indicates it is not thread-safe. For working in a multithreading environment, Java offers a PriorityBlockingQueue class that implements the BlockingQueue interface.

9. It gives O(log(n)) time for enqueuing and dequeuing operations.

10. The iterator produced by the iterator() function does not ensure that it will traverse items in their sorted order.

Java PriorityQueue Example Programs

Let’s examine some sample programs to do different actions based on the aforementioned methods given by Java PriorityQueue.

Program source code 1:

import java.util.Iterator;
import java.util.PriorityQueue;
public class PriorityQueueEx {	
public static void main(String[] args)
{	
// Create a Queue. This priority queue stores Strings objects.  
   PriorityQueue<String> pq = new PriorityQueue<>();
   
// Adds elements to the priority queue.
   pq.offer("USA");
   pq.offer("India");
   pq.offer("England");
   pq.offer("Germany");
   pq.offer("Australia");

System.out.println("Priority queue: " +pq);

// Iterating elements of priority queue.
   System.out.println("Iterating elements of priority queue");
   Iterator<String> iterator = pq.iterator();
   while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
   }
 }
}

Priority queue: [Australia, England, India, USA, Germany]
Iterating elements of priority queue
Australia England India USA Germany

Explanation: As you will note in the output of the preceding program when you print the queue, its items are not arranged according to their priority.

This is because a queue is never used to iterate through its items. PriorityQueue class does not ensure any ordering of items when we use an iterator. Therefore, when we print the priority queue, its items are not sorted according to their priority.

However, when we will use peek() or remove() function, the proper element will be looked at or deleted, which is depending on the element’s priority.

Let’s construct a program where we will peek or delete the proper piece depending on priority.

Program source code 2:

import java.util.PriorityQueue;
public class PriorityQueueEx2 {	
public static void main(String[] args)
{	 
PriorityQueue<String> pq = new PriorityQueue<>();
   
   pq.offer("USA");
   pq.offer("India");
   pq.offer("England");
   pq.offer("Germany");
   pq.offer("Australia");

System.out.println("Elements in queue: " +pq);   

while (pq.peek() != null) {
   System.out.println("Head Element: " + pq.peek());
   System.out.println("Removed Element from Queue: " +pq.remove());
   System.out.println("Priority queue: " + pq);
   }
 }
}

Elements in queue: [Australia, England, India, USA, Germany]
Head Element: Australia
Removed Element from Queue: Australia
Priority queue: [England, Germany, India, USA]
Head Element: England
Removed Element from Queue: England
Priority queue: [Germany, USA, India]
Head Element: Germany
Removed Element from Queue: Germany
Priority queue: [India, USA]
Head Element: India
Removed Element from Queue: India
Priority queue: [USA]
Head Element: USA
Removed Element from Queue: USA
Priority queue: []

Explanation: As you can note in the output, when we use the peek() and remove() methods, the proper element is looked at and deleted from the queue, which is dependent on the element’s priority.

This is because PriorityQueue removes one element from it, processes that element, and then removes another element.

Conclusion

PriorityQueue is a powerful and versatile data structure available in Java that allows developers to manage elements in a queue based on their priority. With its various methods and functionalities, PriorityQueue can be used to implement a wide range of applications, including sorting algorithms, event-driven simulations, and more.

Hope that this article has addressed the essential topics related to PriorityQueue in Java with sample programs. We hope that you would have comprehended this concept using real-time examples.

Frequently Asked Questions

1. What is a PriorityQueue in Java?

PriorityQueue is a class in Java that implements a queue data structure in which elements are ordered based on their natural ordering or a custom comparator.

2. How does PriorityQueue work?

PriorityQueue works by adding elements to the queue using the add() method. The elements are ordered based on their natural ordering or a custom comparator. The element at the head of the queue can be retrieved using the peek() method or removed using the poll() method.

3. What are the advantages of using a PriorityQueue?

PriorityQueue offers several advantages, such as efficient insertion and removal of elements, automatic ordering of elements, and efficient access to the head of the queue.

4. When should I use a PriorityQueue in Java?

PriorityQueue is a useful data structure when you need to maintain a collection of elements in a specific order, such as in sorting or job scheduling. It is also useful when you need to retrieve the highest or lowest element in the collection quickly. However, it is not suitable for scenarios where random access to elements is required, such as in searching.