En Java, el PriorityQueue
La clase se implementa como un montón de prioridad. Heap es una estructura de datos importante en informática. Para obtener una descripción general rápida del montón, aquí es un muy buen tutorial.
1. Ejemplo simple
Los siguientes ejemplos muestran las operaciones básicas de PriorityQueue como offer (), peek (), poll () y size ().
import java.util.Comparator;
import java.util.PriorityQueue;
public class PriorityQueueTest {
static class PQsort implements Comparator<Integer> {
public int compare(Integer one, Integer two) {
return two - one;
}
}
public static void main(String[] args) {
int[] ia = { 1, 10, 5, 3, 4, 7, 6, 9, 8 };
PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>();
// use offer() method to add elements to the PriorityQueue pq1
for (int x : ia) {
pq1.offer(x);
}
System.out.println("pq1: " + pq1);
PQsort pqs = new PQsort();
PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(10, pqs);
// In this particular case, we can simply use Collections.reverseOrder()
// instead of self-defined comparator
for (int x : ia) {
pq2.offer(x);
}
System.out.println("pq2: " + pq2);
// print size
System.out.println("size: " + pq2.size());
// return highest priority element in the queue without removing it
System.out.println("peek: " + pq2.peek());
// print size
System.out.println("size: " + pq2.size());
// return highest priority element and removes it from the queue
System.out.println("poll: " + pq2.poll());
// print size
System.out.println("size: " + pq2.size());
System.out.print("pq2: " + pq2);
}
}
|
import java.util.Comparator; import java.util.PriorityQueue; public class PriorityQueueTest {clase estática PQsort implementa Comparator {public int compare (Integer one, Integer two) {return two – one; }} public static void main (String[] argumentos) {int[] ia = {1, 10, 5, 3, 4, 7, 6, 9, 8}; PriorityQueue pq1 = new PriorityQueue (); // usa el método offer () para agregar elementos a PriorityQueue pq1 for (int x: ia) {pq1.offer (x); } System.out.println («pq1:» + pq1); PQsort pqs = nuevo PQsort (); PriorityQueue pq2 = new PriorityQueue (10, pqs); // En este caso particular, simplemente podemos usar Collections.reverseOrder () // en lugar del comparador autodefinido para (int x: ia) {pq2.offer (x); } System.out.println («pq2:» + pq2); // tamaño de impresión System.out.println («tamaño:» + pq2.size ()); // devuelve el elemento de mayor prioridad en la cola sin eliminarlo System.out.println («peek:» + pq2.peek ()); // tamaño de impresión System.out.println («tamaño:» + pq2.size ()); // devuelve el elemento de mayor prioridad y lo elimina de la cola System.out.println («poll:» + pq2.poll ()); // tamaño de impresión System.out.println («tamaño:» + pq2.size ()); System.out.print («pq2:» + pq2); }}
Producción:
pq1: [1, 3, 5, 8, 4, 7, 6, 10, 9]
pq2: [10, 9, 7, 8, 3, 5, 6, 1, 4]
size: 9
peek: 10
size: 9
poll: 10
size: 8
pq2: [9, 8, 7, 4, 3, 5, 6, 1]
2. Ejemplo de resolución de problemas con PriorityQueue
Fusión de k lista ordenada.
Para obtener más detalles sobre PriorityQueue, vaya a Doc.