PriorityQueue in Java



Java Java Queue PriorityQueue

PriorityQueue in Java

The PriorityQueue in Java is a class that implements the Queue interface and process data based on the priority. It follows the First-In-First-Out concept which means we insert the elements through the rear and delete them through the front. It sorts the elements in the natural order or based on the comparator that we use. The PriorityQueue class is present in the java.util package.

Features of PriorityQueue

  • The size of the queue grows dynamically
  • The initial capacity is 11 but we can modify it using the constructor
  • We cannot store null values.
  • By default, it follows the natural order for sorting.
  • We can use the comparator within the constructor to implement custom sorting order.
  • It is not thread-safe
  • Time complexity is O(log(n)) for insert and poll methods.

PriorityQueue Hierarchy

PriorityQueue in Java

Constructors

ConstructorDescription
PriorityQueue()Creates a PriorityQueue with default capacity 11
PriorityQueue(Collection c)Creates a PriorityQueue with the specified collection elements
PriorityQueue(int capacity)Creates a PriorityQueue with the specified capacity
PriorityQueue(int capacity, Comparator comparator)Creates a PriorityQueue with the specified capacity and orders the elements based on the mentioned comparator.
PriorityQueue(PriorityQueue q)Creates a PriorityQueue with the specified PriorityQueue elements
PriorityQueue(SortedSet s)Creates a PriorityQueue with the specified elements in the SortedSet

Methods

The PriorityQueue class inherits methods from the Queue, Collection, and Object.

MethodDescriptionParameter
Boolean add(String e)Adds the specified element to the end of the queuee - the element to be added.
Return value - True
Boolean addAll(Collection c)Adds a collection of specified elements to the queue.c - collection of elements to be added
Return value - true
void clear()Clears all the elements in the queue.
Boolean contains(Object o)Checks if the queue contains the specified elementReturn value - true if the queue contains the element
Boolean containsAll(Collection c)Checks if the queue contains all the elements in the collectionReturn value - true if the queue contains all the elements
Object element()Returns the first element(head) in the queue
Boolean equals(Object o)Compares if the queue contains all the specified elements in the exact orderReturn value - true if object elements match with the queue
Boolean isEmpty()Checks if the queue is empty or notReturn value - true if queue contains no values
Iterator iterator()Retrieves the iterator of queue in sequenceReturn value - Iterator
Boolean offer(Object e)Inserts the element as the taile - element to be added
Object peek()Retrieves the first element of the queue(head)Returns null if the queue is empty
Object poll()Retrieves and removes the first element of the queue(head)Returns null if the queue is empty
Object remove()Removes the first element from the queue
Boolean remove(Object o)Removes the first occurrence of the specified object from the queue if presento - The element that needs to be removed
Return value - true if queue contains the element
Boolean removeAll(Collection c)Removes the first occurrence of all the elements in the collection from the queue if presentc - collection of elements
Return value - true if the queue contains the collection
Boolean retainAll(Collection c)Retains all the elements specified in collection in queue. Other elements will be removedc - collection of elements that has to be retained
Return value - true if the queue changed due to the method called
int size()Fetches the size of the queueReturn value - size of the queue
Spliterator spliterator()Returns a spliterator over the elements in the queue
Object[] toArray()Returns an array of elements in proper sequenceReturn value - Array of all elements in the queue in proper sequence
String toString()Returns a String representation of the elements collectionReturn value - String of array elements separated by comma and space and enclosed within []

Example: Insert elements in PriorityQueue

The below example shows how to insert elements in a PriorityQueue using the add() and addAll() methods. We can also use the offer() method to insert a value into a PriorityQueue in Java.

import java.util.PriorityQueue;

public class InsertPriorityQueueElements {

  public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(30);
    pq.add(20);
    pq.add(10);
    pq.add(40);
    
    System.out.println("Elements in the PriorityQueue after add method: " + pq);
    
    PriorityQueue<Integer> p = new PriorityQueue<Integer>();
    p.add(60);
    p.add(50);
    
    pq.addAll(p);
    
    System.out.println("Elements in the PriorityQueue after addAll method: " + pq);

    pq.offer(70);
    System.out.println("Elements in the PriorityQueue after offer method: " + pq);

  }

}
Elements in the PriorityQueue after add method: [10, 30, 20, 40]
Elements in the PriorityQueue after addAll method: [10, 30, 20, 40, 50, 60]
Elements in the PriorityQueue after offer method: [10, 30, 20, 40, 50, 60, 70]

Example: Delete elements from PriorityQueue

The below example illustrates how to delete a specific value from the PriorityQueue in Java using the remove() method. To delete a collection of elements, we can use the removeAll() method. The poll() method returns and removes the head element from the queue.

import java.util.PriorityQueue;

public class DeletePriorityQueueElements {

  public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(30);
    pq.add(20);
    pq.add(10);
    pq.add(40);
    
    System.out.println("Elements in the PriorityQueue after add method: " + pq);
    
    PriorityQueue<Integer> p = new PriorityQueue<Integer>();
    p.add(60);
    p.add(50);
    
    pq.addAll(p);
    
    System.out.println("Elements in the PriorityQueue after addAll method: " + pq);
    
    pq.remove();
    System.out.println("Elements in the PriorityQueue after remove method: " + pq);
    
    pq.remove(40);
    System.out.println("Elements in the PriorityQueue after remove method: " + pq);
    
    pq.removeAll(p);
    System.out.println("Elements in the PriorityQueue after removeAll method: " + pq);
    
    System.out.println("Element returned and deleted by the poll method: " + pq.poll());

  }

}
Elements in the PriorityQueue after add method: [10, 30, 20, 40]
Elements in the PriorityQueue after addAll method: [10, 30, 20, 40, 50, 60]
Elements in the PriorityQueue after remove method: [20, 30, 60, 40, 50]
Elements in the PriorityQueue after remove method: [20, 30, 60, 50]
Elements in the PriorityQueue after removeAll method: [20, 30]
Element returned and deleted by the poll method: 20

Example: Access elements in a Java PriorityQueue

We can use the iterator method to traverse through every element in the PriortyQueue in Java. To access the head element, we use the peek() method. The below example shows how to access and traverse through values.

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

public class IteratePriorityQueueElements {

  public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(30);
    pq.add(20);
    pq.add(10);
    pq.add(40);
    
    System.out.println("Iterate using the iterator method");
    Iterator<Integer> i = pq.iterator();
    while(i.hasNext())
      System.out.println(i.next());

    System.out.println("Head element using the peek method: " + pq.peek());
    System.out.println("Head element using element method: " + pq.element());
  }

}
Iterate using the iterator method
10
30
20
40
Head element using the peek method: 10
Head element using element method: 10

Example: Check if Java PriorityQueue contains specific values

To check if the PriorityQueue in Java contains a specific element, we can use the contains() method. To check a collection of elements, use the containsAll() method. We can retain only the collection elements and remove other values, use the retainAll() method.

import java.util.PriorityQueue;

public class CheckPriorityQueueValues {

  public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(30);
    pq.add(20);
    pq.add(10);
    pq.add(40);
    
    PriorityQueue<Integer> p = new PriorityQueue<Integer>();
    p.add(60);
    p.add(50);
    
    pq.addAll(p);
    
    System.out.println("Elements in the PriorityQueue: " + pq);
    
    System.out.println(pq.contains(20));
    System.out.println(pq.contains(100));
    System.out.println(pq.containsAll(p));
    
    pq.retainAll(p);
    
    System.out.println("Elements in the PriorityQueue after retainAll method: " + pq);

  }

}
Elements in the PriorityQueue: [10, 30, 20, 40, 50, 60]
true
false
true
Elements in the PriorityQueue after retainAll method: [50, 60]

Example: Clear the Java PriorityQueue and check if empty

The below example shows to clear the PriorityQueue values using the clear() method and check if the queue is empty using the isEmpty() method.

import java.util.PriorityQueue;

public class ClearPriorityQueue {

  public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(30);
    pq.add(20);
    pq.add(10);
    pq.add(40);
    
    System.out.println("Elements in the PriorityQueue: " + pq);
    
    System.out.println("Is Empty: " + pq.isEmpty());
    pq.clear();
    System.out.println("Elements in the PriorityQueue after clear method: " + pq);
    System.out.println("Is Empty: " + pq.isEmpty());

  }

}
Elements in the PriorityQueue: [10, 30, 20, 40]
Is Empty: false
Elements in the PriorityQueue after clear method: []
Is Empty: true

Example: Implement custom ordering using Comparator

We can define our own comparator class to implement custom ordering of values in the PriorityQueue in Java. In the below example, we create SampleComparator.java that returns the largest value as the head of the queue.

import java.util.PriorityQueue;

public class PriorityQueueComparatorDemo {

  public static void main(String[] args) {
    PriorityQueue<Integer> p = new PriorityQueue<Integer>(10, new SampleComparator());
    p.add(60);
    p.add(20);
    p.add(80);
    p.add(10);
    
    System.out.println(p);

  }

}

SampleComparator.java

import java.util.Comparator;
public class SampleComparator implements Comparator<Integer> {

  @Override
  public int compare(Integer x, Integer y) {
    if(x < y)
      return 1;
    else
      return -1;
  }

}
[80, 20, 60, 10]

Example: Creating PriorityQueue with Java objects

We can also create PriorityQueue using Java objects as in the below example. We have a class OrderDetails that implement the Comparable interface. In the overridden method, we display the details based on the order number. In this case, it displays the largest order number first. We need to pass the OrderDetails class as an argument type to the PriorityQueue. Hence it adds the OrderDetails objects to the queue and process based on the Comparator defined where it returns the largest order number as the head value.

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

public class OrderDetails implements Comparable<OrderDetails> {

  int OrderNumber;
  int Amount;
  int quantity;
  
  public static void main(String[] args) {
    OrderDetails o1= new OrderDetails(111, 1000, 5);
    OrderDetails o2 = new OrderDetails(222, 5000, 4);
    OrderDetails o3 = new OrderDetails(333, 3000, 10);
    
    PriorityQueue<OrderDetails> p = new PriorityQueue<>();
    p.add(o1);
    p.add(o2);
    p.add(o3);
    
    Iterator i = p.iterator();
    
    while(i.hasNext())
      System.out.println(i.next());
  }

  @Override
  public int compareTo(OrderDetails o) {
    if(o.OrderNumber > this.OrderNumber)
      return 1;
    else
      return -1;
  }
  
  public OrderDetails(int orderNumber, int Amount, int qty) {
    this.OrderNumber = orderNumber;
    this.Amount = Amount;
    this.quantity = qty;
  }
  
  public String toString() {
    return "Order Number: " + this.OrderNumber + ", Total Amount: " + this.Amount + ", Qty: " + this.quantity;
  }

}
Order Number: 333, Total Amount: 3000, Qty: 10
Order Number: 111, Total Amount: 1000, Qty: 5
Order Number: 222, Total Amount: 5000, Qty: 4

 

Reference