Minimal min-heap

min-heap-ext.js

import {up, down} from './min-heap.js';

// more efficient operations based on up() and down()
// WARNING: untested (if I wrote comprehensive tests it wouldn't be a gist, would it?)

const replaceTop = (heapArray, value, less) => {
  const top = heapArray[0];
  heapArray[0] = value;
  down(heapArray, 0, less);
  return top;
};

const pushPop = (heapArray, value, less) => {
  if (!heapArray.length || less(value, heapArray[0])) return value;
  return replaceTop(heapArray, value, less);
};

const updateByIndex = (heapArray, index, isDecreased, less) => {
  (isDecreased ? up : down)(heapArray, index, less);
};

const removeByIndex = (heapArray, index, less) => {
  if (index === heapArray.length - 1) return heapArray.pop();
  const value = heapArray[index],
    newValue = heapArray[index] = heapArray.pop();
  updateByIndex(heapArray, index, less(newValue, value), less);
  return value;
};

const sortHeap = (heapArray, less) => {
  for (let i = heapArray.length - 1; i > 0; --i) {
    [heapArray[0], heapArray[i]] = [heapArray[i], heapArray[0]];
    down(heapArray, 0, less, i);
  }
};

const makeHeap = (heapArray, less) => {
  for (let i = 1; i < heapArray.length; ++i) {
    up(heapArray, i, less);
  }
};

export {replaceTop, pushPop, updateByIndex, removeByIndex, sortHeap, makeHeap};

min-heap.js

const left = i => (i << 1) + 1;
const right = i => (i + 1) << 1; // left(i) + 1
const parent = i => (i - 1) >> 1;

const up = (heapArray, i, less) => {
  for (let p = parent(i); i > 0; i = p, p = parent(p)) {
    if (!less(heapArray[i], heapArray[p])) break;
    [heapArray[i], heapArray[p]] = [heapArray[p], heapArray[i]]; //swap
  }
};

const down = (heapArray, i, less, size = heapArray.length) => {
  for (;;) {
    const l = left(i), r = l + 1;
    if (l >= size) break;
    const c = r < size && less(heapArray[r], heapArray[l]) ? r : l;
    if (!less(heapArray[c], heapArray[i])) break;
    [heapArray[i], heapArray[c]] = [heapArray[c], heapArray[i]]; //swap
    i = c;
  }
};

class MinHeap {
  constructor(less) {
    this.less = less;
    this.heapArray = [];
  }
  get isEmpty() {
    return !this.heapArray.length;
  }
  get size() {
    return this.heapArray.length;
  }
  get top() {
    return this.heapArray[0];
  }
  push(value) {
    const last = this.heapArray.length;
    this.heapArray.push(value);
    up(this.heapArray, last, this.less);
  }
  pop() {
    if (this.heapArray.length <= 1) return this.heapArray.pop();
    const top = this.heapArray[0];
    this.heapArray[0] = this.heapArray.pop();
    down(this.heapArray, 0, this.less);
    return top;
  }
}

export {left, right, parent, up, down, MinHeap};
export default MinHeap;

test-min-heap.js

import MinHeap from './min-heap.js';

const h = new MinHeap((a, b) => a < b);

const samples = new Array(100);
for (let i = 0; i < samples.length; ++i) {
  samples[i] = Math.floor(100 * Math.random());
}

for (const sample of samples) {
  h.push(sample);
}

console.log({isEmpty: h.isEmpty, size: h.size, top: h.top, heapArray: h.heapArray});

const result = [];
while (!h.isEmpty) {
  result.push(h.pop());
}

console.log({result});

samples.sort((a, b) => a - b);

let sorted = true;
for (let i = 0; i < samples.length; ++i) {
  if (samples[i] !== result[i]) {
    sorted = false;
    break;
  }
}

console.log({sorted});