Requisito previo: Cola de prioridad, Cola de prioridad del comparador
es como una cola normal, pero cada elemento tiene una «prioridad» asociada. En una cola de prioridad, un elemento con alta prioridad se sirve antes que un elemento con baja prioridad. Para ello utiliza una función de comparación que impone una ordenación total de los elementos.
Los elementos de la cola de prioridad se ordenan de acuerdo con su ordenación natural, o mediante un Comparador proporcionado en el momento de la construcción de la cola, según el constructor que se utilice
. Constructores:
- public PriorityQueue() : Esto crea un PriorityQueue con la capacidad inicial predeterminada (11) que ordena sus elementos según su orden natural.
- public PriorityQueue(Collection c) : Esto crea un PriorityQueue que contiene los elementos en la colección especificada (c). Si la colección especificada es una instancia de SortedSet, esta cola de prioridad se ordenará de acuerdo con el mismo orden; de lo contrario, esta cola de prioridad se ordenará de acuerdo con el orden natural de sus elementos.
- public PriorityQueue(int capacity, Comparator comparador) : Esto crea un PriorityQueue con la capacidad inicial especificada que ordena sus elementos de acuerdo con el comparador especificado.
Parameters: capacity - the initial capacity for this priority queue comparator - the comparator that will be used to order this priority queue. If null, the natural ordering of the elements will be used.
- public PriorityQueue(SortedSet ss) : crea un PriorityQueue que contiene los elementos del conjunto ordenado especificado. Esta cola de prioridad se ordenará de acuerdo con el mismo orden que el conjunto ordenado dado.
El código de muestra provisto ilustra que los estudiantes con alta prioridad (basado en cgpa) son atendidos antes que los estudiantes que tienen un cgpa bajo.
// Java program to demonstrate working of
// comparator based priority queue constructor
import java.util.*;
public class Example {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
// Creating Priority queue constructor having
// initial capacity=5 and a StudentComparator instance
// as its parameters
PriorityQueue<Student> pq = new
PriorityQueue<Student>(5, new StudentComparator());
// Invoking a parameterized Student constructor with
// name and cgpa as the elements of queue
Student student1 = new Student("Nandini", 3.2);
// Adding a student object containing fields
// name and cgpa to priority queue
pq.add(student1);
Student student2 = new Student("Anmol", 3.6);
pq.add(student2);
Student student3 = new Student("Palak", 4.0);
pq.add(student3);
// Printing names of students in priority order,poll()
// method is used to access the head element of queue
System.out.println("Students served in their priority order");
while (!pq.isEmpty()) {
System.out.println(pq.poll().getName());
}
}
}
class StudentComparator implements Comparator<Student>{
// Overriding compare()method of Comparator
// for descending order of cgpa
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;
// A parameterized student constructor
public Student(String name, double cgpa) {
this.name = name;
this.cgpa = cgpa;
}
public String getName() {
return name;
}
}
Students served in their priority order Palak Anmol Nandini
Nota: este tipo de cola de prioridad se prefiere en escenarios donde se requiere un orden personalizado, es decir, cuando uno quiere un orden de clasificación diferente, entonces uno puede definir su propia forma de comparar instancias. El comparador se puede implementar si existe un algoritmo de comparación más complejo, por ejemplo, múltiples campos, etc.