Java PriorityQueue

PriorityQueue<E> es el heap del JDK. Es una Queue, pero en lugar de FIFO el cabezal siempre es el elemento menor según un Comparator (u orden natural si no proporcionas uno). offer es O(log n), poll y peek desde el cabezal son O(log n) y O(1) respectivamente, y el almacenamiento subyacente es un array plano — sin asignación de nodos por elemento. Eso lo convierte en la herramienta adecuada para problemas con forma de planificador: "siempre trabajar en lo que sea más urgente a continuación."

Qué significa "cabezal" aquí

Para una cola FIFO, el cabezal es quien llegó primero. Para una PriorityQueue, el cabezal es quien tiene el valor menor en este momento — no el menor en el momento de inserción:

• peek() devuelve el actual menor.
• poll() elimina el actual menor y reequilibra; el siguiente peek muestra el nuevo menor.
• offer(x) inserta y reequilibra; si x es el nuevo menor, el siguiente peek lo devuelve.

"Menor" se decide por:

1. El Comparator que pasaste al constructor, si existe.
2. De lo contrario, el orden natural del elemento mediante Comparable. Si tus elementos no son Comparable y no pasaste un Comparator, la primera llamada que necesite comparar lanza ClassCastException.

No hay modo de heap máximo. Si quieres un max-heap, pasa Comparator.reverseOrder() (o tu comparador personalizado invertido) — ese es el idioma estándar y lo usamos en el ejemplo siguiente.

Construir uno

// Natural order (Comparable elements).
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Reversed for max-heap behaviour.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom comparator — by length, then alphabetically.
PriorityQueue<String> byLen = new PriorityQueue<>(
    Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

// Pre-sized + comparator (initial capacity must come first).
PriorityQueue<String> bigByLen = new PriorityQueue<>(1_000,
    Comparator.comparingInt(String::length));

// From an existing collection.
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));

El constructor de un solo argumento que toma una Collection es O(n) — heapifica en bloque en lugar de n offers de O(log n). Útil cuando ya tienes todos los datos por adelantado.

La iteración NO está en orden de prioridad

Esta es la sorpresa con la que la mayoría de la gente se encuentra una vez. Iterar una PriorityQueue recorre el array heap subyacente en el orden que el heap almacena sus nodos — no en orden ascendente:

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));
System.out.println(pq);                // possibly [10, 20, 30, 40]
for (int x : pq) System.out.print(x + " "); // possibly: 10 20 30 40
                                            // possibly: 10 40 30 20

El orden de impresión es un detalle de implementación del diseño del heap. Si quieres elementos en orden de prioridad, tienes que vaciar:

while (!pq.isEmpty()) System.out.print(pq.poll() + " ");   // sorted

Ten esto en cuenta cuando uses forEach, stream, toArray, o simplemente imprimas la cola para depuración. El Stream devuelto por stream() no está ordenado, y agregar .sorted() requiere que los elementos sean Comparable (o puedes pasar un comparador).

Mutar un elemento después de offer rompe el heap

La prioridad se calcula en el momento de la inserción. Si introduces un elemento y luego mutes el campo que el comparador observa, el heap está ahora en un estado inválido — poll puede devolver el cabezal incorrecto, contains puede fallar, pierdes el invariante. No existe un método update o decrease-key.

Las dos soluciones alternativas:

• Usa elementos inmutables — records con campos de prioridad, o records envolventes como record Task(int priority, String name) {}. Entonces no hay nada que mutar después de la inserción.
• Elimina y reinserta si realmente necesitas cambiar la prioridad: pq.remove(task) es O(n) (busca), luego pq.offer(taskWithNewPriority) es O(log n).

Para una cola pequeña, eliminar y reinsertar está bien. Para "estoy reescribiendo el algoritmo de Dijkstra y necesito decrease-key rápido", una PriorityQueue no es la herramienta adecuada — quieres un heap indexado o un TreeSet de pares (priority, node).

null y seguridad de hilos

Las mismas reglas que el resto de Queue:

• Sin nulos. pq.offer(null) lanza NullPointerException.
• No es seguro para hilos. El acceso concurrente necesita PriorityBlockingQueue, el primo de java.util.concurrent.

Un ejemplo trabajado: un pequeño planificador de tareas

El programa siguiente usa una PriorityQueue para planificar tareas por prioridad (número menor = más urgente). También muestra el idioma de max-heap y la sorpresa del orden de iteración.

Leyendo la ejecución:

• toString() y forEach mostraron las tareas en algún orden — no ordenado. No uses ninguno de los dos para depurar "¿está bien la prioridad?" — vacía con poll para ver el orden real.
• El constructor masivo produjo un heap correctamente ordenado de una sola vez — esa es la ruta de heapify en tiempo lineal.
• El bloque de mutación al final es el error peligroso en forma concentrada. Mutamos la prioridad del array después de ofrecerlo, el heap no tuvo oportunidad de reequilibrarse, y ahora peek está mintiendo. La solución es usar un envolvente inmutable o hacer remove-y-offer después del cambio.

Qué sigue

El próximo capítulo cubre la implementación a la que recurres cuando quieres una cola FIFO o una pila o un deque — y la que el Javadoc del JDK te orienta a usar como predeterminada para los tres: ArrayDeque. Es la clase que hace la mayor parte del trabajo en segundo plano en el código de ejemplo de los dos capítulos anteriores.

Práctica