Heaps y colas de prioridad

¿Qué es un heap?

Un heap es un árbol binario completo donde cada nodo cumple la propiedad del heap. En un Max Heap, padre ≥ hijos. En un Min Heap, padre ≤ hijos. ¡Los heaps son perfectos para colas de prioridad!

Implementación de Min Heap

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }

  bubbleDown(index) {
    while (true) {
      let minIndex = index;
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;
      
      if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[minIndex]) {
        minIndex = leftChild;

  

    
Aprende más
    

      
        
GeeksforGeeks: Heap
        
Entiende heaps y colas de prioridad.
      
      
        
LeetCode: Heap
        
Resuelve problemas de heaps y colas de prioridad.
      
    
  

      }
      if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[minIndex]) {
        minIndex = rightChild;
      }
      if (minIndex === index) break;
      
      [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
      index = minIndex;
    }
  }

  peek() {
    return this.heap[0];
  }
}