Heap y Priority Queue

Un Heap es una estructura de árbol binario con una propiedad especial: en un Min-Heap el padre siempre es menor que sus hijos, por lo que la raíz siempre es el elemento mínimo. En un Max-Heap el padre siempre es mayor, y la raíz es el máximo.

La ventaja es que puedes obtener el mínimo o máximo en O(1) (leer la raíz). Insertar un elemento y extraer el mínimo/máximo tarda O(log n), porque debes reordenar el árbol para mantener la propiedad.

La aplicación más importante del Heap es la Priority Queue (cola de prioridad): una cola donde el elemento con mayor prioridad siempre sale primero, sin importar en qué orden llegaron.

Se usa en el algoritmo de Dijkstra para caminos más cortos (siempre procesa el nodo más cercano primero), en el scheduling de tareas del sistema operativo, y en el problema "encuentra los K elementos más grandes" que se resuelve elegantemente con un Min-Heap de tamaño K.

// Min-Heap implementado
class MinHeap {
  #heap = [];
  
  get size() { return this.#heap.length; }
  get min() { return this.#heap[0]; }
  
  insertar(val) {
    this.#heap.push(val);
    this.#subirBurbuja(this.#heap.length - 1);
  }
  
  extraerMin() {
    if (this.size === 1) return this.#heap.pop();
    const min = this.#heap[0];
    this.#heap[0] = this.#heap.pop();
    this.#bajarBurbuja(0);
    return min;
  }
  
  #subirBurbuja(i) {
    while (i > 0) {
      const padre = Math.floor((i - 1) / 2);
      if (this.#heap[padre] <= this.#heap[i]) break;
      [this.#heap[padre], this.#heap[i]] = [this.#heap[i], this.#heap[padre]];
      i = padre;
    }
  }
  
  #bajarBurbuja(i) {
    while (true) {
      let min = i;
      const izq = 2 * i + 1, der = 2 * i + 2;
      if (izq < this.size && this.#heap[izq] < this.#heap[min]) min = izq;
      if (der < this.size && this.#heap[der] < this.#heap[min]) min = der;
      if (min === i) break;
      [this.#heap[i], this.#heap[min]] = [this.#heap[min], this.#heap[i]];
      i = min;
    }
  }
}

// Problemas clásicos con Heap

// K elementos más grandes - O(n log k)
function kMasGrandes(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.insertar(n);
    if (heap.size > k) heap.extraerMin(); // Mantener solo k elementos
  }
  return heap.min; // El k-ésimo mayor
}

// Merge k listas ordenadas - O(n log k)
function mergeKListas(listas) {
  // En JS, simular con array + sort (heap sería más eficiente)
  return listas.flat().sort((a, b) => a - b);
}

// Python tiene heapq nativo:
// import heapq
// heapq.heappush(heap, val)   → insertar
// heapq.heappop(heap)         → extraer mínimo
// heapq.nlargest(k, iterable) → k más grandes
// heapq.nsmallest(k, iterable) → k más pequeños