Binary heap in JavaScript

binary-heap.js

module.exports = { push, pop, heap }

function push(heap, el, cmp = _cmp) {
  let i = heap.length;
  heap.push(el);
  while (i > 0) {
    const parent = Math.ceil(i / 2) - 1;
    if (cmp(heap[i], heap[parent]) > 0) {
      break;
    }
    [heap[i], heap[parent]] = [heap[parent], heap[i]];
    i = parent;
  }
}

function pop(heap, cmp = _cmp) {
  if (heap.length === 0) {
    return;
  }
  const size = heap.length-1;
  [heap[0], heap[size]] = [heap[size], heap[0]];
  const el = heap.pop();
  let i = 0;
  while (i < size-1) {
    const left = i*2 + 1;
    const right = i*2 + 2;
    let child;
    if (right < size && cmp(heap[left], heap[right]) > 0) {
      child = right;
    } else if (left < size) {
      child = left;
    } else {
      break;
    }
    if (cmp(heap[child], heap[i]) > 0) {
      break;
    }
    [heap[i], heap[child]] = [heap[child], heap[i]];
    i = child;
  }
  return el;
}

function heap(cmp = _cmp) {
  const heap = [];
  return {
    heap,
    size() {
      return heap.length;
    },
    push(el) {
      push(heap, el, cmp);
    },
    pop() {
      return pop(heap, cmp);
    }
  }
}

function _cmp(a, b) {
  return a - b;
}