Java Priority Queue Tutorial – Implementation & Examples

This Tutorial Explains the Java Priority Queue and related Concepts like Comparator, Min, and Max Priority Queue along with its Implementation with Examples:

Priority Queue data structure is a special queue in which the elements are present not as per FIFO order but according to the natural elements or any custom comparator used during queue creation.

=> Take A Look At The Java Beginners Guide Here.

Priority Queue In Java

In Priority Queue, the front of the queue has the least elements as per the natural ordering and the rear is pointed to the greatest element in the queue.

An example Priority Queue consisting of numbers is shown below.

Thus when an element is removed from the priority queue shown above, then it will be the least element.

Similarly, for an alphabetical priority queue, ASCII values will be considered and the queue elements will be ordered as per the ASCII values.

Enlisted below are some of the major characteristics of the PriorityQueue:

• PriorityQueue is an unbound queue.
• PriorityQueue does not allow null values.
• For non-comparable objects, we cannot create a priority queue.
• PriorityQueue inherits from the classes like AbstractQueue, AbstractCollection, Collection, and Object.
• The head or front of the queue contains the least element as per the natural ordering.
• Priority Queue implementation is not thread-safe. Thus if we desire synchronized access, we should use the PriorityBlockingQueue.

The PriorityQueue class inherits Java Queue Interface and is a part of the java.util package.

The general declaration of the PriorityQueue class is given below:

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

The below diagram shows the class hierarchy for the PriorityQueue class.

Time Complexity of Priority Queue

1. The time complexity of Priority Queue for insertion(enqueue) and deletion (dequeue) methods, is O(log(n)).
2. Priority Queue has linear time complexity for remove as well as contains methods.
3. The methods that retrieve elements of the Priority Queue have constant time complexity.

Priority Queue Example In Java

The below program demonstrates a simple PriorityQueue in Java. We create an object of PriorityQueue class, add values to it, and then display the contents of the Queue using Iterator.

import java.util.*;

class Main{  
    public static void main(String args[]){  
        PriorityQueue<String> cities_queue=new PriorityQueue<String>();  
        //initialize the PriorityQueue with values
        cities_queue.add("Sydney");  
        cities_queue.add("Venice");  
        cities_queue.add("New York");  
        cities_queue.add("California");  
        cities_queue.add("Melbourne");  
        //print the head of the PriorityQueue
        System.out.println("PriorityQueue Head:"+cities_queue.element());  
        //Define the iterator for PriorityQueue and print its elements 
        System.out.println("\nPriorityQueue contents:");  
        Iterator iter=cities_queue.iterator();  
        while(iter.hasNext()){ 
            System.out.print(iter.next() + " ");  
        }  
    }  
}  

Output:

Java Priority Queue API Methods

Constructors:

Methods

Implementation In Java

Let’s  demonstrate the above methods of PriorityQueue using a Java program.

import java.util.*; 
  
class Main { 
    public static void main(String args[])  { 
        // Creating empty priority queue 
        PriorityQueue<String> numQueue = new PriorityQueue<String>(); 
        // add elements to numQueue using add() 
        numQueue.add("Five"); 
        numQueue.add("One"); 
        numQueue.add("Seven"); 
        numQueue.add("Three"); 
        numQueue.add("Eleven");
        numQueue.add("Nine"); 
  
        // Print the head element using Peek () method 
        System.out.println("Head element using peek method:"  + numQueue.peek()); 
  
        // Printing all elements 
        System.out.println("\n\nThe PriorityQueue elements:"); 
        Iterator iter1 = numQueue.iterator(); 
        while (iter1.hasNext()) 
            System.out.print(iter1.next() + " "); 
  
        // remove head with poll () 
        numQueue.poll(); 
        System.out.println("\n\nAfter removing an element" +  "with poll function:"); 
        Iterator<String> iter2 = numQueue.iterator(); 
        while (iter2.hasNext()) 
            System.out.print(iter2.next() + " "); 
  
        // Remove 'Three' using remove ()
        numQueue.remove("Three"); 
        System.out.println("\n\nElement 'Three' with"
                           + " remove function:"); 
        Iterator<String> iter3 = numQueue.iterator(); 
       
      while (iter3.hasNext()) 
            System.out.print(iter3.next() + " "); 
  
        // Check if an element is present in PriorityQueue using contains() 
        boolean ret_val = numQueue.contains("Five"); 
        System.out.println("\n\nPriority queue contains 'Five' "
                           + "or not?: " + ret_val); 
  
        // get array equivalent of PriorityQueue with toArray () 
        Object[] numArr = numQueue.toArray(); 
        System.out.println("\nArray Contents: "); 
        for (int i = 0; i < numArr.length; i++) 
            System.out.print(numArr[i].toString() + " "); 
    } 
}

Output:

Priority Queue In Java 8

Java 8 adds one more method to PriorityQueue class i.e. ‘spliterator ()’.

The details of this method are given below.

Method Name: spliterator

Method Prototype: public final Spliterator<E> spliterator ()

Method Description: This method creates a spliterator over the PriorityQueue elements. This spliterator is late-binding and fail-fast.

Priority Queue Comparator

As already mentioned PriorityQueue elements are naturally ordered. If we want to change the ordering, then we should specify a comparator and use it during the creation of the PriorityQueue object. The PriorityQueue then uses this comparator to order its elements.

The below Java program demonstrates the use of custom comparator for element ordering. In this program, we define a new custom comparator inside which we override the ‘compare’ method. The compare method is used to order the elements of the PriorityQueue according to the length.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // A custom comparator that compares two Strings by their length.
        Comparator<String> customComparator = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }
        };
        // Create a Priority Queue with a custom Comparator
        PriorityQueue<String> colorsPriorityQueue = new PriorityQueue<>(customComparator);

        // Add items to a Priority Queue
        colorsPriorityQueue.add("Red");
        colorsPriorityQueue.add("Green");
        colorsPriorityQueue.add("Blue");
        colorsPriorityQueue.add("Cyan");
        colorsPriorityQueue.add("Magenta");
        colorsPriorityQueue.add("Yellow");

// Printing all elements 
        System.out.println("\nThe PriorityQueue elements with custom Comparator:"); 
        Iterator iter1 = colorsPriorityQueue.iterator(); 
        while (iter1.hasNext()) 
            System.out.print(iter1.next() + " "); 
    }
}

Output:

Min Priority Queue In Java

The natural ordering of Priority Queue has the least or smallest element at the head of the queue and thus the ordering is ascending. This is called the “Min priority queue” with ascending order of elements.

The Java program below shows the implementation of the Min Priority Queue in Java.

import java.util.*;

class Main{  
    public static void main(String args[]){ 
        //declare a PriorityQueue object with default ordering
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        //add element to the PriorityQueue
        pq.add(8);  
        pq.add(6);  
        pq.add(4); 
        pq.add(2);  
        pq.add(12);  
        pq.add(10);
        //display the min PriorityQueue
        System.out.println("The min Priority Queue (natural ordering) contents:");
        Integer val = null;
        while( (val = pq.poll()) != null) {
            System.out.print(val + " ");
        }
    }  
}  

Output:

Max Priority Queue in Java

While the min priority queue has elements in ascending order, the max priority queue has the elements in descending order i.e. the head of the Max priority queue will return the greatest element in the queue.

The Java program below demonstrates the Max Priority Queue in Java.

import java.util.*;

class Main{  
    public static void main(String args[]){ 
        //declare a PriorityQueue object with custom comparator to generate max PQ
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer lhs, Integer rhs) {
                if (lhs < rhs) return +1;
                if (lhs.equals(rhs)) return 0;
                    return -1;
            }
        });
        //add element to the PriorityQueue
        pq.add(8);  
        pq.add(6);  
        pq.add(4); 
        pq.add(2);  
        pq.add(12);  
        pq.add(10);
        //display the max PriorityQueue
        System.out.println("The max Priority Queue contents:");
        Integer val = null;
        while( (val = pq.poll()) != null) {
            System.out.print(val + " ");
        }
    }  
}   

Output:

As shown in the above program, to change the natural ordering of elements in the priority queue, we have to define a custom comparator.

Frequently Asked Questions

Q #1) What is the Priority queue in Java?

Answer: A special queue in which all the elements of the queue are ordered as per natural ordering or using a custom comparator is called the Priority queue. It does not follow the FIFO order.

Q #2) How do you set a Max Priority queue in Java?

Answer: We can set a Max Priority Queue in Java using a custom comparator so that the head of the queue will return the largest element in the queue.

Q #3) Does the Priority queue allow duplicates Java?

Answer: Yes. Priority Queue allows duplicate values.

Q #4) Is Java Priority queue max or min?

Answer: By default, the priority queue in Java is min Priority queue with natural ordering. To make it max, we have to use a custom comparator so that head of the queue returns the greatest element in the queue.

Q #5) Is a Priority Queue sorted?

Answer: By default, the head of the queue is sorted and the Priority queue has the least element as its head. The rest of the elements is ordered when required.

Conclusion

This completes the tutorial on Priority Queues in Java. Priority Queue implements a queue interface and is a special queue where elements are ordered as per natural ordering. It does not follow the FIFO order. To change the natural ordering of the priority queue, we can use the custom comparator.

Priority queues are mainly used for Printer scheduling, CPU task scheduling, etc. The heap (min or max) is also implemented using Priority Queues.

=> Read Through The Easy Java Training Series.