Min Heap

MinHeap.js

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

  insert(x) {
    this.arr.push(x);
    this.bubbleUp(this.arr.length - 1);
  }

  pop() {
    const min = this.arr[0];
    [this.arr[0], this.arr[this.arr.length - 1]] = [this.arr[this.arr.length - 1], this.arr[0]];
    this.arr.pop();
    this.bubbleDown(0);
    return min;
  }

  left(node) {
    return node * 2 + 1;
  }

  right(node) {
    return node * 2 + 2;
  }

  parent(node) {
    return Math.floor((node - 1) / 2);
  }

  bubbleDown(node) {
    let min = node;
    if (this.arr[this.left(node)] < this.arr[node]) {
      min = this.left(node);
    }
    if (this.arr[this.right(node)] < this.arr[node]) {
      min = this.right(node);
    }
    if (min !== node) {
      [this.arr[node], this.arr[min]] = [this.arr[min], this.arr[node]];
      this.bubbleDown(min);
    }
  }

  bubbleUp(node) {
    if (this.parent(node) >= 0 && this.arr[this.parent(node)] > this.arr[node]) {
      [this.arr[this.parent(node)], this.arr[node]] = [this.arr[node], this.arr[this.parent(node)]];
      this.bubbleUp(this.parent(node));
    }
  }
}