Java PriorityQueue

In this tutorial, we will learn about what is java.util.PriorityQueue, how it is different from other Queue's and use cases of it along with working examples.

PriorityQueue class

The java.util.PriorityQueue class in Java is an implementation of the Queue interface and It is used to store a collection of elements in a queue and the elements are ordered based on their natural sorting ordering or according to the ordering specified by using custom comparator.

In a priority queue, the element with the highest priority is always at the front of the queue and becomes head of the queue and the one to be removed first.

PriorityQueue compareTo() method:

The elements of a priority queue are ordered based on the natural sorting ordering of the elements (as determined by their compareTo() method), or by a Comparator provided at the time of creation of the priority queue instance. Comparator allows to use custom logic to determine order of the elements which is equivalent to priority of the elements.

PriorityQueue use cases:

Some of the use cases of the PriorityQueue class are:

1. It can be used to implement scheduling algorithms where the tasks with higher priority are executed first.
2. It can be used in graph algorithms, such as Dijkstra's algorithm, where we need to prioritize the vertices based on their distance from the starting vertex.
3. It can be used in event-driven simulation systems where events are stored in a priority queue and the next event to be processed is the one with the highest priority.

Example 1:

The following is an example of using the java.util.PriorityQueue class.

Copied

import java.util.PriorityQueue;
public class PriorityQueueExample {
    public static void main(String[] args) {
        // Create a priority queue and add elements to it
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(10);
        pq.add(20);
        pq.add(15);
        pq.add(5);
        // Print the contents of the priority queue
        System.out.println("Priority Queue: " + pq);
        // Remove the elements from the priority queue
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
    }
}

Output:

Priority Queue: [5, 10, 15, 20]
5 10 15 20

Explanation:

In the above example, we first created a PriorityQueue instance and add four elements to it. The elements of type Integer class and then print the contents of the priority queue and remove the elements from it using the poll() method. As expected, the elements of Integer type are printed in ascending order.

Example 2:

Copied

import java.util.PriorityQueue;
public class PriorityQueueExampleString {
    public static void main(String[] args) {
        PriorityQueue<String> priorityQueue = new PriorityQueue<>();
        priorityQueue.add("John");
        priorityQueue.add("Adam");
        priorityQueue.add("Sarah");
        priorityQueue.add("Mike");
        System.out.println("Priority queue elements: " + priorityQueue);
        System.out.println("Peek: " + priorityQueue.peek());
        System.out.println("Remove: " + priorityQueue.remove());
        System.out.println("Priority queue after removing an element: " + priorityQueue);
        priorityQueue.add("David");
        System.out.println("Priority queue after adding an element: " + priorityQueue);
        System.out.println("Poll: " + priorityQueue.poll());
        System.out.println("Priority queue after polling an element: " + priorityQueue);
        System.out.println("Element: " + priorityQueue.element());
        System.out.println("Priority queue after getting the element: " + priorityQueue);
    }
}

Output:

Priority queue elements: [Adam, John, Sarah, Mike]
Peek: Adam
Remove: Adam
Priority queue after removing an element: [John, Mike, Sarah]
Priority queue after adding an element: [David, John, Sarah, Mike]
Poll: David
Priority queue after polling an element: [John, Mike, Sarah]
Element: John
Priority queue after getting the element: [John, Mike, Sarah]

Explanation:

In the above example, we created PriorityQueue with element type as String and added four elements to it. Although PriorityQueue implementation of Queue interface but follows natural order, to check these printed elements of Queue and having the natural order of String.

Later used peek() method to examine the head of the Queue its returned "Adam". Later we performed other operations of the Queue and examined the order of the Queue by printing its elements.

Conclusion:

In this tutorial, we have covered what is PriorityQueue class and how its different from the traditional Queue, how order of the elements gets priority along with working examples of it.