Min-heap functional style

minHeap-fn.js

/**
  * Min heap priority queue implementation
  *
  * @param  {Array}  [arr] [[]]
  * @param  {function (a:number, b:number)} [cmp] [function (a, b) { return a - b; }] Comparator
  * @return {Object}
  */
const heap = function (arr, cmp = (a, b) => a - b) {

    /**
     * @type {Array}
     */
    arr = arr || [];

    /**
     * Heap size
     * @type {number}
     */
    let size = arr.length;

    /**
     * Array swap
     * @param  {Array.<number>} [arr]
     * @param  {number} x
     * @param  {number} y
     */
    const swap = (array, x, y) => {
      let tmp  = array[x];
      array[x] = array[y];
      array[y] = tmp;
    };

    /**
     * Index of the parent node
     * @param  {number} index
     * @return {number}
     */
    const parent = (index) => Math.floor((index - 1) / 2);

    /**
     * Get index of left child of node at index
     * @param  {number} index
     * @return {number}
     */
    const left =   (index) => 2 * index + 1;

    /**
     * Get index of right child of node at index
     * @param  {number} index
     * @return {number}
     */
    const right =  (index) => 2 * index + 2;


    /**
     * Heapify a subtree with root at given index
     * @param  {number} i
     */
    function heapify (i) {
      let l = left(i);
      let r = right(i);
      let smallest = i;
      if (l < size && cmp(arr[l], arr[i]) < 0)        smallest = l;
      if (r < size && cmp(arr[r], arr[smallest]) < 0) smallest = r;
      if (smallest !== i) {
        swap(arr, i, smallest);
        heapify(smallest);
      }
    }

    let heap = {

      heapify,

      /**
       * Extract the minimum element
       * @return {*}
       */
      pop () {
        if (size <= 0) return undefined;
        if (size === 1) {
          size--;
          return arr[0];
        }

        // Store the minimum value, and remove it from heap
        let root = arr[0];
        arr[0] = arr[size - 1];
        size--;
        heapify(0);

        return root;
      },

      /**
       * Decreases key value of key at index i to value,
       * assuming it's smaller than the current value
       * @param {number} i index
       * @param {*} value
       */
      decreaseKey (i, value) {
        arr[i] = value;
        while (i != 0 && cmp(arr[parent(i)], arr[i]) > 0) {
          swap(arr, i, parent(i));
          i = parent(i);
        }
      },

      /**
       * Minimum element, root
       * @return {*}
       */
      min () {
        return arr[0];
      },

      /**
       * Deletes a key stored at index
       * first put the element at root, than pop ()
       * @param {number} index
       * @return {*}
       */
      remove (index) {
        this.decreaseKey(index, Number.NEGATIVE_INFINITY);
        return this.pop();
      },

      /**
       * New element
       * @param {*} val
       */
      push (val) {
        // First insert the new key at the end
        size++;
        let i  = size - 1;
        arr[i] = val;

        // Fix the min heap property if it is violated
        while (i !== 0 && cmp(arr[parent(i)], arr[i], parent(i), i, size) > 0) {
          swap(arr, i, parent(i));
          i = parent(i);
        }
      },

      /**
       * Checks if the queue is empty
       * @return {boolean}
       */
      empty () {
        return size <= 0;
      },


      toArray () {
        return arr.slice(0, size);
      }
    };

    Object.defineProperty(heap, 'size', {
      get: () => size,
      enumerable: true
    });

    return heap;
  };