Last Updated on December 14, 2022 by Prepbytes
Priority Queue:
Priority queue is an abstract data type, It is a type of queue in which each element has a priority assigned to it. The priority of the element determines the order in which elements are removed from the priority queue. In the priority queue, all the elements are arranged either in ascending order or descending order.
Priority Queue Properties:
- In the priority queue, every element has priority assigned to it.
- The element with highest priority first.
- If two elements are having the same priority then they are served according to their order in the queue.
Priority Queue Comparator method:
Priority queue comparator function is used to return the order of the elements that are stored in the priority queue Comparator method returns the null value if the queue follows the same order of the elements.
Syntax:
Comp_set = (PriorityQueue)Priority_Queue.comparator()Comparator method does not take any parameters.
Implementation 1: Using natural order of the elements.
import java.util.*;
class Priority_Queue_Demo {
public static void main(String[] args)
{
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
queue.add(2);
queue.add(24);
queue.add(3);
queue.add(35);
queue.add(45);
queue.add(50);
System.out.println("Priority queue values are: " + queue);
Comparator comp = queue.comparator();
System.out.println("Since the Comparator value is: " + comp);
System.out.println("Because it follows natural ordering");
}
}
Implementation 2: Using the specific comparator.
import java.util.Comparator; import java.util.PriorityQueue; class The_Comparator implements Comparator{ public int compare(String str1, String str2) { String first_Str; String second_Str; first_Str = str1; second_Str = str2; return second_Str.compareTo(first_Str); } } class Priority_Queue_Demo { public static void main(String[] args) { PriorityQueue queue = new PriorityQueue (new The_Comparator()); queue.add("P"); queue.add("R"); queue.add("E"); queue.add("P"); queue.add("4"); System.out.println("The elements with the highest priority element at front of queue" + "order:"); while(!queue.isEmpty()){ System.out.print(" "+queue.poll()); } } }
While implementing the priority queue using a comparator function the elements of the priority queue are ordered according to their natural order or by using a comparator provided at the construction time.
And it depends which constructor we are using:
-
Public PriorityQueue(): It creates a priority queue with default capacity that orders its elements according to their order.
-
Public PriorityQueue(int initialCapacity, Comparator \
comparator): It creates a priority queue with the specified initial capacity in which elements are ordered in accordance to their specified comparator -
Public PriorityQueue(SortedSet
PQ): It Creates a priority queue containing all the elements in the sorted set. -
PriorityQueue(Collection
C): It creates a priority queue containing all the elements in a specified collection.
Implementation of priority queue using comparator method:
import java.util.*;
class Example {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
PriorityQueue pq = new
PriorityQueue(5, new StudentComparator());
Student student1 = new Student("Ankit", 3.2);
pq.add(student1);
Student student2 = new Student("Amit", 3.6);
pq.add(student2);
Student student3 = new Student("Pal", 4.0);
pq.add(student3);
System.out.println("Students served in their priority order");
while (!pq.isEmpty()) {
System.out.println(pq.poll().getName());
}
}
}
class StudentComparator implements Comparator{
public int compare(Student s1, Student s2) {
if (s1.cgpa < s2.cgpa)
return 1;
else if (s1.cgpa > s2.cgpa)
return -1;
return 0;
}
}
class Student {
public String name;
public double cgpa;
public Student(String name, double cgpa) {
this.name = name;
this.cgpa = cgpa;
}
public String getName() {
return name;
}
}
This article tried to discuss the concept of Implementing Priority Queue Comparator using Java. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming at Prepbytes