min heap

minheap.js

function minHeap (cmp, arr = []) {

  const up = (i) => {
    let object = arr[i];
    while (i > 0) {
      let up     = ((i + 1) >> 1) - 1,
          parent = arr[up];
      if (cmp(object, parent) >= 0) break;
      arr[parent.index = i] = parent;
      arr[object.index = i = up] = object;
    }
  };

  const down = (i) => {
    let object  = arr[i];
    while (true) {
      let right = (i + 1) << 1,
          left  = right - 1,
          down  = i,
          child = arr[down],
          len   = arr.length;
      if (left  < len && cmp(arr[left], child)  < 0) child = arr[down = left];
      if (right < len && cmp(arr[right], child) < 0) child = arr[down = right];
      if (down === i) break;
      arr[child.index  = i]        = child;
      arr[object.index = i = down] = object;
    }
  };

  return {

    push (...args) {
      for (let i = 0, n = args.length; i < n; ++i) {
        let object = arguments[i];
        up(object.index = arr.push(object) - 1);
      }
      return arr.length;
    },

    pop () {
      const removed = arr[0];
      let object = arr.pop();
      if (arr.length) {
        arr[object.index = 0] = object;
        down(0);
      }
      return removed;
    },

    remove (removed) {
      const i = removed.index;
      let object = arr.pop();

      if (i !== arr.length) {
        arr[object.index = i] = object;
        (cmp(object, removed) < 0 ? up : down)(i);
      }
      return i;
    }
  };
}