MinHeap

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

  size() {
    return this.heap.length;
  }

  insert(node) {
    this.heap.push(node);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;

    while (idx > 0) {
      let parent = Math.floor((idx - 1) / 2);

      if (this.heap[parent].val <= this.heap[idx].val) {
        break;
      }

      [this.heap[parent], this.heap[idx]] =
        [this.heap[idx], this.heap[parent]];

      idx = parent;
    }
  }

  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();

    return min;
  }

  bubbleDown() {
    let idx = 0;

    while (true) {
      let smallest = idx;

      let left = idx * 2 + 1;
      let right = idx * 2 + 2;

      if (
        left < this.heap.length &&
        this.heap[left].val < this.heap[smallest].val
      ) {
        smallest = left;
      }

      if (
        right < this.heap.length &&
        this.heap[right].val < this.heap[smallest].val
      ) {
        smallest = right;
      }

      if (smallest === idx) break;

      [this.heap[idx], this.heap[smallest]] =
        [this.heap[smallest], this.heap[idx]];

      idx = smallest;
    }
  }
}