Heaps y el K-ésimo mayor elemento en Java: algoritmos con PriorityQueue

Los heaps aparecen en muchos algoritmos clásicos y en bastantes preguntas de entrevista técnica. En Java no necesitas implementarlos desde cero: PriorityQueue ya te da un heap funcional con las operaciones que necesitas. El truco está en saber cuándo usarlo y cómo configurarlo.

Qué es un heap

Un heap es un árbol binario casi completo que cumple la propiedad de orden del heap: cada nodo es mayor o igual que sus hijos (max-heap) o menor o igual que sus hijos (min-heap). Esa restricción garantiza que el elemento extremo (el mayor o el menor) siempre está en la raíz y se puede consultar en O(1).

"Casi completo" significa que todos los niveles están rellenos excepto quizá el último, que se rellena de izquierda a derecha. Eso permite almacenar el árbol en un array sin punteros, lo que lo hace muy eficiente en memoria.

PriorityQueue en Java

PriorityQueue implementa un min-heap por defecto: el elemento con menor valor natural (o según el comparador que pases) siempre está en la cabeza. Las operaciones principales:

• offer(e) / add(e): inserta un elemento. Complejidad O(log n).
• poll(): extrae y devuelve el elemento de la cabeza (el mínimo). O(log n).
• peek(): devuelve el elemento de la cabeza sin extraerlo. O(1).
• size(): número de elementos. O(1).

Para un max-heap, pasa Collections.reverseOrder() al constructor:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

O un comparador lambda si los elementos son objetos:

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]); // orden descendente por índice 1

Problema 1: el K-ésimo mayor elemento

Dado un array de enteros, encuentra el K-ésimo mayor. Por ejemplo, en [3, 2, 1, 5, 6, 4] con K=2, la respuesta es 5.

Solución naive con Arrays.sort()

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

Funciona, pero ordena el array completo: O(n log n). Si solo necesitas el K-ésimo mayor no tiene sentido ordenar todo.

Solución óptima con min-heap de tamaño K

La idea: mantén un min-heap con los K elementos más grandes vistos hasta ahora. La raíz del heap es el menor de esos K, que es exactamente el K-ésimo mayor.

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // descarta el menor
        }
    }

    return minHeap.peek(); // el menor de los k mayores = el k-ésimo mayor
}

Complejidad: O(n log k). Por cada elemento hacemos como mucho una inserción y una extracción en un heap de tamaño k. Cuando n es grande y k es pequeño, la diferencia respecto a O(n log n) es significativa.

Problema 2: top K elementos más frecuentes

Dado un array, devuelve los K elementos que aparecen con más frecuencia. Para [1, 1, 1, 2, 2, 3] con K=2, la respuesta es [1, 2].

El enfoque combina un HashMap para contar frecuencias y un heap para seleccionar los K más frecuentes:

public int[] topKFrequent(int[] nums, int k) {
    // 1. Contar frecuencias
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }

    // 2. Min-heap ordenado por frecuencia (la menor frecuencia queda en la raíz)
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(
        (a, b) -> freq.get(a) - freq.get(b)
    );

    // 3. Mantener solo los k más frecuentes
    for (int num : freq.keySet()) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }

    // 4. Extraer resultado
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = minHeap.poll();
    }
    return result;
}

Complejidad: O(n log k). Primero construimos el mapa de frecuencias en O(n) y luego recorremos las claves únicas manteniendo el heap de tamaño k.

Heaps en casos reales

Más allá de las entrevistas, los heaps aparecen en varios lugares del software de producción:

• Colas de prioridad para tareas: procesar primero las tareas con mayor prioridad sin reordenar la cola completa cada vez que llega una nueva.
• Algoritmo de Dijkstra: el min-heap permite extraer siempre el nodo con menor distancia acumulada. Sin heap, el algoritmo degrada a O(V²).
• Merge de K listas ordenadas: insertar el primer elemento de cada lista en un min-heap y extraer en bucle. O(n log k) donde k es el número de listas.
• Planificadores y sistemas de eventos: los eventos se ordenan por timestamp y el heap garantiza acceso O(1) al siguiente evento a procesar.

Truco: mediana en un stream de datos

Un problema clásico: mantener la mediana de un flujo de números que llegan uno a uno. No puedes ordenar el array completo cada vez que llega un número.

La solución usa dos heaps:

• Un max-heap para la mitad inferior (los números pequeños). La raíz es el mayor de la mitad inferior.
• Un min-heap para la mitad superior (los números grandes). La raíz es el menor de la mitad superior.

class MedianFinder {
    private PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    private PriorityQueue<Integer> upper = new PriorityQueue<>(); // min-heap

    public void addNum(int num) {
        lower.offer(num);
        upper.offer(lower.poll()); // equilibra: el mayor de lower pasa a upper

        if (lower.size() < upper.size()) {
            lower.offer(upper.poll()); // mantiene lower >= upper en tamaño
        }
    }

    public double findMedian() {
        if (lower.size() > upper.size()) {
            return lower.peek();
        }
        return (lower.peek() + upper.peek()) / 2.0;
    }
}

Cada inserción es O(log n) y consultar la mediana es O(1). Para grandes volúmenes de datos en tiempo real es una solución muy eficiente.

Heap vs TreeSet vs array ordenado

Los tres guardan elementos ordenados, pero tienen trade-offs distintos:

• Heap: inserción y extracción del extremo en O(log n), acceso al extremo en O(1). No permite buscar un elemento arbitrario ni recorrerlo en orden sin destruirlo. Ideal cuando solo necesitas el mínimo o máximo continuamente.
• TreeSet: inserción, borrado y búsqueda en O(log n). Permite recorrerlo en orden, buscar el primer elemento mayor que X, etc. Más flexible pero con mayor constante oculta en la práctica.
• Array ordenado: acceso por índice en O(1), búsqueda binaria en O(log n), pero inserción en O(n) por el desplazamiento. Solo tiene sentido si el array es estático o casi estático.

Para el K-ésimo mayor o el top K, el heap es la opción natural. Para rangos, consultas por valor o recorrido ordenado, TreeSet o TreeMap son más adecuados.

Preguntas de entrevista sobre heaps en Java

Algunos patrones que aparecen con frecuencia y qué esperan los entrevistadores:

• K-ésimo mayor/menor: esperan que menciones el heap de tamaño K y justifiques O(n log k) frente a O(n log n) con sort. Si mencionas QuickSelect también sumas puntos (O(n) en promedio).
• Merge de K listas: esperan el min-heap con un nodo por lista. Que sepas que la complejidad es O(n log k) donde n es el total de elementos.
• Mediana en stream: esperan los dos heaps. Es una solución que no es obvia y demuestra que conoces la estructura en profundidad.
• Diferencia entre heap y BST: heap garantiza O(1) para el mínimo/máximo pero no soporta búsquedas arbitrarias. BST soporta O(log n) para cualquier clave.

Conocer bien PriorityQueue encaja con dominar las patrones de diseño en Java, complemento ideal para estructuras de datos cuando construyes sistemas donde la eficiencia importa. Y si trabajas con Java 25 LTS, PriorityQueue sigue siendo exactamente la misma clase con la misma API que en Java 8, así que todo lo de esta guía aplica sin cambios.

La referencia completa de la clase está en la documentación oficial de Java 21, con todos los constructores, métodos y notas de implementación.

Imagen: Pexels / Markus Spiske