Java — Priority Queue | Code Factory

Donate : Link

WordPress Blog : Link

A Priority Queue in Java is a special type of queue wherein all the elements are ordered as per their natural ordering or based on a custom Comparator supplied at the time of creation.

The front of the priority queue contains the least element according to the specified ordering, and the rear of the priority queue contains the greatest element.

So when you remove an element from the priority queue, the least element according to the specified ordering is removed first.

The Priority Queue class is part of Java’s collections framework and implements the Queue interface. Following is the class hierarchy of the Priority Queue class in Java.

Example 1 :

Let’s create a Priority Queue of integers and add some integers to it. After adding the integers, we’ll remove them one by one from the priority queue and see how the smallest integer is removed first followed by the next smallest integer and so on.

package com.example.java.programming.queue;
import java.util.PriorityQueue;
/**
 * @author code.factory
 *
 */
public class PriorityQueueExample {
	public static void main(String[] args) {
		// Create a Priority Queue
		PriorityQueue<Integer> numbers = new PriorityQueue<>();
		// Add items to a Priority Queue (ENQUEUE)
		numbers.add(680);
		numbers.add(160);
		numbers.add(160);
		numbers.add(750);
		numbers.add(420);
		numbers.add(680);
		numbers.add(34);
		// Remove items from the Priority Queue (DEQUEUE)
		while (!numbers.isEmpty()) {
			System.out.println(numbers.remove());
		}
	}
}

Output :

34
160
160
420
680
680
750

Example 2 :

package com.example.java.programming.queue;
import java.util.PriorityQueue;
/**
 * @author code.factory
 *
 */
public class PriorityQueueExample {
	public static void main(String[] args) {
		// Create a Priority Queue
		PriorityQueue<String> numbers = new PriorityQueue<>();
		// Add items to a Priority Queue (ENQUEUE)
		numbers.add("Narendra");
		numbers.add("Amit");
		numbers.add("Yogi");
		numbers.add("Smriti");
		numbers.add("Rajnath");
		// Remove items from the Priority Queue (DEQUEUE)
		while (!numbers.isEmpty()) {
			System.out.println(numbers.remove());
		}
	}
}

Output :

Amit
Narendra
Rajnath
Smriti
Yogi

Creating a Priority Queue with a custom Comparator :

Let’s say that we need to create a priority queue of String elements in which the String with the smallest length is processed first.

We can create such a priority queue by passing a custom Comparator that compares two Strings by their length.

Here is an example -

package com.example.java.programming.queue;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
 * @author code.factory
 *
 */
public class PriorityQueueExample {
	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();
            }
        };
        /*
        The above Comparator can also be created using lambda expression like this =>
        Comparator<String> stringLengthComparator = (s1, s2) -> {
            return s1.length() - s2.length();
        };
        Which can be shortened even further like this =>
        Comparator<String> stringLengthComparator = Comparator.comparingInt(String::length);
        */
        // Create a Priority Queue with a custom Comparator
		PriorityQueue<String> numbers = new PriorityQueue<>(stringLengthComparator);
		// Add items to a Priority Queue (ENQUEUE)
		numbers.add("Narendra");
		numbers.add("Amit");
		numbers.add("Yogi");
		numbers.add("Smriti");
		numbers.add("Rajnath");
		// Remove items from the Priority Queue (DEQUEUE)
		while (!numbers.isEmpty()) {
			System.out.println(numbers.remove());
		}
	}
}

Output :

Amit
Yogi
Smriti
Rajnath
Narendra

Priority Queue of user defined objects :

In this example, you’ll learn how to create a priority queue of user defined objects.

Since a priority queue needs to compare its elements and order them accordingly, the user defined class must implement the Comparable interface, or you must provide a Comparator while creating the priority queue. Otherwise, the priority queue will throw a ClassCastException when you add new objects to it.

Check out the following example in which we create a priority queue of a custom class called Employee. The Employee class implements the Comparable interface and compares two employees by their salary.

package com.example.java.programming.queue;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;
/**
 * @author code.factory
 *
 */
public class PriorityQueueExample {
	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<Employee> employees = new PriorityQueue<>();
		// Add items to a Priority Queue (ENQUEUE)
		employees.add(new Employee("Narendra", 50000));
		employees.add(new Employee("Amit", 45000));
		employees.add(new Employee("Yogi", 25000));
		employees.add(new Employee("Smriti", 30000));
		employees.add(new Employee("Rajnath", 35000));
		// Remove items from the Priority Queue (DEQUEUE)
		while (!employees.isEmpty()) {
			System.out.println(employees.remove());
		}
	}
}
class Employee implements Comparable<Employee> {
    private String name;
    private double salary;
    public Employee(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;
        Employee employee = (Employee) o;
        return Double.compare(employee.salary, salary) == 0 &&
                Objects.equals(name, employee.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, salary);
    }
    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", salary=" + salary +
                '}';
    }
    // Compare two employee objects by their salary
    @Override
    public int compareTo(Employee employee) {
        if(this.getSalary() > employee.getSalary()) {
            return 1;
        } else if (this.getSalary() < employee.getSalary()) {
            return -1;
        } else {
            return 0;
        }
    }
}

Output :

Employee{name='Yogi', salary=25000.0}
Employee{name='Smriti', salary=30000.0}
Employee{name='Rajnath', salary=35000.0}
Employee{name='Amit', salary=45000.0}
Employee{name='Narendra', salary=50000.0}

Notice how the Employee with the lowest salary is removed first.