Min Heap

MIN HEAP

heap operations

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

  // Insert a new value into the heap
  insert(value) {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
    return this.heap;
  }

  // Delete and return the minimum value (root) from the heap
  deleteMin() {
    if (this.heap.length === 0) {
      return null;
    }
    const minValue = this.heap[0];
    const lastValue = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = lastValue;
      this.heapifyDown(0);
    }
    return minValue;
  }

  // Heapify up to maintain heap property after insertion
  heapifyUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] > this.heap[index]) {
        [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
        index = parentIndex;
      } else {
        break;
      }
    }
    return this.heap;
  }

  // Heapify down to maintain heap property after deletion
  heapifyDown(index) {
    const length = this.heap.length;
    while (true) {
      const leftIndex = 2 * index + 1;
      const rightIndex = 2 * index + 2;
      let smallestIndex = index;

      if (leftIndex < length && this.heap[leftIndex] < this.heap[smallestIndex]) {
        smallestIndex = leftIndex;
      }
      if (rightIndex < length && this.heap[rightIndex] < this.heap[smallestIndex]) {
        smallestIndex = rightIndex;
      }
      if (smallestIndex !== index) {
        [this.heap[index], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[index]];
        index = smallestIndex;
      } else {
        break;
      }
    }
  }

  // Get the minimum value without removing it
  getMin() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  // Check if the heap is empty
  isEmpty() {
    return this.heap.length === 0;
  }
}

// Usage example
const heap = new MinHeap();
heap.insert(4);
heap.insert(7);
heap.insert(1);
heap.insert(23);
heap.insert(9);
console.log("Heap after inserts:", heap.insert(34));

console.log("Minimum value:", heap.getMin());
console.log("Remove min:", heap.deleteMin());
console.log("New heap after deleting min:", heap.heap);
console.log("New minimum value:", heap.getMin());
console.log("Is heap empty?", heap.isEmpty());