Java 58: PriorityQueue & the Binary Heap
easy⏱ 5 mincoursejava
Heap binario en array
Un heap binario es un árbol completo aplanado en un array: para el índice i, los hijos están en 2i+1 y 2i+2, el padre en (i-1)/2. La invariante de heap para un min-heap: cada padre ≤ sus hijos, así el mínimo siempre está en el índice 0. Sin punteros, gran localidad de caché — el array es el árbol.
PriorityQueue<Integer> pq = new PriorityQueue<>(); // min-heap
pq.add(5); pq.add(1); pq.add(3);
pq.peek(); // 1 (smallest, O(1))
pq.poll(); // 1 (remove smallest, O(log n))
// max-heap: new PriorityQueue<>(Comparator.reverseOrder())
sift-up (insertar) y sift-down (poll)
Insertar: añade al final, luego sift up — intercambia con el padre mientras sea menor — O(log n). Poll: toma el índice 0 (el mín), mueve el último elemento a la raíz, luego sift down — intercambia con el hijo menor mientras sea mayor — O(log n). Ambos tocan solo un camino raíz-a-hoja, por eso un heap gana al ordenamiento cuando solo necesitas los primeros pocos.
Top-K con un heap acotado
Para hallar los K más pequeños de N elementos en O(N log K) (no O(N log N)), mantén un max-heap de tamaño K: empuja cada elemento; si el tamaño excede K, saca el mayor. Lo que queda son los K más pequeños. (Simétricamente, un min-heap de tamaño K da los K más grandes.) Es la técnica estándar de top-K en streaming — nunca tienes los N ordenados.
Construye un min-heap, luego heapsort
Implementa MinHeap con push (sift-up) y pop (sift-down) sobre un array. Empuja [5, 3, 8, 1, 9, 2] y confirma que peek() es 1. Luego haz pop() repetidamente hasta vaciar para obtener una secuencia ordenada ascendente 1 2 3 5 8 9 (eso es heapsort). Imprime el peek, la salida ordenada y el array interno tras los pushes para mostrar que no está totalmente ordenado, solo heap-ordenado.
No iteres una PriorityQueue esperando orden
for (x : pq) y pq.toArray() recorren el array interno, que está heap-ordenado, no ordenado — solo la cabeza se garantiza la más pequeña. Para consumir en orden debes poll repetidamente (que la vacía) o copiar a una lista y ordenar. Esto confunde a muchos en entrevistas.
Quiz: complejidad de peek vs poll
¿Cuáles son las complejidades de PriorityQueue.peek() y poll()? peek es O(1) (el mín siempre está en el índice 0); poll es O(log n) (debe mover el último elemento a la raíz y hacer sift-down para restaurar la invariante). Insertar (add) también es O(log n).