Java Priority Queue Tutorial with Examples

Priority Queue Java Implementation

A PriorityQueue is usually needed when the elements are processed as per their priority. As we all know that a Queue works on the basis
of First-in-First-Out basis. But at times the elements of the queue are required to be processed as per their priority,
that is where the PriorityQueue comes into picture.The PriorityQueue underlying uses priority heap. Elements of the priority queue are ordered
as per the natural ordering or we can provide a Comparator during queue creation time.

Front side of the priority queue has the least element as per the specified ordering and the rear of the priority queue has the largest element.
Hence, when you remove an element from the priority queue the least element as per the specified ordering is removed first.

PriorityQueue implements the Queue interface and it part of the collection framework.

PriorityQueue Hierarchy:

java-priority-queue-class-hierarchy

Some of the important points on Priority Queue are

  • PriorityQueue doesn’t store NULL pointers.
  • We can not create PriorityQueue of Objects which are not comparable
  • PriorityQueue are unbound queues of elements.
  • The operations like poll, remove, peek will be at the element at the head of the queue.

Constructors of PriorityQueue class

  • PriorityQueue(): Creates a PriorityQueue with the default initial capacity of 11 .
  • PriorityQueue(Collection<E> p): Creates a PriorityQueue having the elements in the specified collection.
  • PriorityQueue(int initialCapacity): Creates a PriorityQueue with the specified initial capacity.
  • PriorityQueue(int initialCapacity, Comparator<E> comparator): Creates a PriorityQueue with the specified initial capacity that orders its elements as per the given comparator.
  • PriorityQueue(PriorityQueue<E> p): Creates a PriorityQueue having the elements in the given priority queue.
  • PriorityQueue(SortedSet<E> p): Creates a PriorityQueue having the elements in the given sorted set.

Creating a Priority Queue with Basic Operations

//Program to demonstrate working of priority queue in Java 
import java.util.*;

class PriorityQueueExample 
{ 
public static void main(String args[]) 
{ 
// Creating empty priority queue 
PriorityQueue<String> pQueue = new PriorityQueue<String>();

// Adding items to the pQueue using add() 
pQueue.add("Ashish"); 
pQueue.add("Rahul"); 
pQueue.add("Vivek"); 
pQueue.add("Amit");

// Printing the most priority element 
System.out.println("Head value using peek function:"+ pQueue.peek());

// Printing all elements 
System.out.println("The queue elements:"); 
Iterator itr = pQueue.iterator(); 
while (itr.hasNext()) 
System.out.println(itr.next());

// Removing the top priority element (or head) and 
// printing the modified pQueue using poll() 
pQueue.poll(); 
System.out.println("After removing an element" + 
" with poll function:"); 
Iterator<String> itr2 = pQueue.iterator(); 
while (itr2.hasNext()) 
System.out.println(itr2.next());

// Removing Java using remove() 
pQueue.remove("Java"); 
System.out.println("after removing Java with" + 
" remove function:"); 
Iterator<String> itr3 = pQueue.iterator(); 
while (itr3.hasNext()) 
System.out.println(itr3.next());

// Check if an element is present using contains() 
boolean b = pQueue.contains("C"); 
System.out.println ( "Priority queue contains C " + 
"or not?: " + b);

// Getting objects from the queue using toArray() 
// in an array and print the array 
Object[] arr = pQueue.toArray(); 
System.out.println ( "Value in array: "); 
for (int i = 0; i<arr.length; i++) 
System.out.println ( "Value: " + arr[i].toString()) ; 
} 
} 

Output: -

Head value using peek function:Amit
The queue elements:
Amit
Ashish
Vivek
Rahul
After removing an element with poll function:
Ashish
Rahul
Vivek
after removing Java with remove function:
Ashish
Rahul
Vivek
Priority queue contains C or not?: false
Value in array: 
Value: Ashish
Value: Rahul
Value: Vivek

Creating a Priority Queue with a custom Comparator

Suppose we need to create a priority queue of String elements in which the String with the smallest length is processed first.

We can create this  priority queue by passing a custom Comparator  as argument which will compare two Strings as per their length.

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueCustomComparatorExample {
public static void main(String[] args) {
// A custom comparator that compares two Strings by their length.
Comparator<String> stringLengthComparator = 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> namePriorityQueue = new PriorityQueue<>(stringLengthComparator);

// Add items to a Priority Queue (ENQUEUE)
namePriorityQueue.add("Chandler");
namePriorityQueue.add("Ross");
namePriorityQueue.add("Rachel");
namePriorityQueue.add("Joey");
namePriorityQueue.add("Phoebe");
namePriorityQueue.add("Monica");

// Remove items from the Priority Queue (DEQUEUE)
while (!namePriorityQueue.isEmpty()) {
System.out.println(namePriorityQueue.remove());
}
}
}

Output:-

Ross
Joey
Phoebe
Monica
Rachel
Chandler

Priority Queue having User defined objects

The user defined class should implement the Comparable interface or you should provide a Comparator during creation of the priority queue.

Lets make priority queue of a custom class called Employee.

import java.util.Objects;
import java.util.PriorityQueue;

class Employee1 implements Comparable<Employee1> {
private String name;
private double salary;

public Employee1(String name, double salary) {
this.name = name;
this.salary = salary;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public double getSalary() {
return salary;
}

public void setSalary(double salary) {
this.salary = salary;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Employee1 Employee1 = (Employee1) o;
return Double.compare(Employee1.salary, salary) == 0 &&
Objects.equals(name, Employee1.name);
}

@Override
public int hashCode() {
return Objects.hash(name, salary);
}

@Override
public String toString() {
return "Employee1{" +
"name='" + name + '\'' +
", salary=" + salary +
'}';
}

// Compare two Employee1 objects by their salary
@Override
public int compareTo(Employee1 Employee1) {
if(this.getSalary() > Employee1.getSalary()) {
return 1;
} else if (this.getSalary() < Employee1.getSalary()) {
return -1;
} else {
return 0;
}
}
}

Now creating the main PriorityQueue Class:

import java.util.PriorityQueue;

public class PriorityQueueUserDefinedObjectExample {
public static void main(String[] args) {
/*
The requirement for a PriorityQueue of user defined objects is that

1. Either the class should implement the Comparable interface and provide
the implementation for the compareTo() function.
2. Or you should provide a custom Comparator while creating the PriorityQueue.
*/

// Create a PriorityQueue
PriorityQueue<Employee1> Employee1PriorityQueue = new PriorityQueue<>();

// Add items to the Priority Queue
Employee1PriorityQueue.add(new Employee1("Ram", 100000.00));
Employee1PriorityQueue.add(new Employee1("Arun", 145000.00));
Employee1PriorityQueue.add(new Employee1("Rahul", 115000.00));
Employee1PriorityQueue.add(new Employee1("Joey", 167000.00));

/*
The compareTo() method implemented in the Employee1 class is used to determine
in what order the objects should be dequeued.
*/
while (!Employee1PriorityQueue.isEmpty()) {
System.out.println(Employee1PriorityQueue.remove());
}
}
}

Output:-

Employee1{name=’Ram’, salary=100000.0}
Employee1{name=’Rahul’, salary=115000.0}
Employee1{name=’Arun’, salary=145000.0}
Employee1{name=’Joey’, salary=167000.0}

PriorityQueue peek() Method in Java

peek() method in PriorityQueue is used to get or fetch  the element present at the head of the Queue. The element fetched will not get deleted or removed from the Queue.

Return Value: The method returns the element at the head of the Queue otherwise returns NULL value if the Queue is empty.

PriorityQueue poll() Method in Java

poll() method in PriorityQueue is used to get or fetch and remove the head element of the Queue .

Return Value: The method returns the element at the head of the Queue otherwise returns NULL value if the Queue is empty.

Conclusion

We have learnt that how to create the PriorityQueue its basic operations. How to use the PriorityQueue in Custom class as object.

We have also learnt how to use the Comparator in PriorityQueue .

 

One Comment on “Java Priority Queue Tutorial with Examples”

Leave a Reply

Your email address will not be published. Required fields are marked *