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:
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 .
Which function can we use to print output in descending/inverse order?