Heaps & Priority Queues

What is a Heap?

A heap is a complete binary tree where each node satisfies the heap property. In a Max Heap, parent ≥ children. In a Min Heap, parent ≤ children. Heaps are perfect for priority queues!

Min Heap Implementation

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;

  

    
Learn More
    

      
        
GeeksforGeeks: Heap
        
Understanding Heap data structure and Priority Queues.
      
      
        
LeetCode: Heap
        
Solve problems involving Heaps and Priority Queues.
      
    
  

      }
      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];
  }
}