Min-heap OOP style

minHeap-oop.js

 
// Prototype of a utility function to swap two integers
const swap = (arr, x, y) => {
  let tmp = arr[x];
  arr[x]  = arr[y];
  arr[y]  = tmp;
};

const parent = (index) => Math.floor((index - 1) / 2);
 
// to get index of left child of node at index i
const left = (index) => 2 * index + 1;
 
// to get index of right child of node at index i
const right = (index) => 2 * index + 2;
 
// A class for Min Heap
class MinHeap {
  
  constructor (arr, cmp = (a, b) => a - b) {
    this._arr  = arr || []; // pointer to array of elements in heap
    this._size = this._arr.length; // Current number of elements in min heap
    this._cmp  = cmp;
    if (this._size > 0) {
      this.heapify(0);
    }
  }
  
  get size () {
    return this._size;
  }
  
    // to heapify a subtree with root at given index
  heapify (i) {
    let l = left(i);
    let r = right(i);
    let smallest = i;
    let arr = this._arr;
    let size = this._size;
    if (l < size && arr[l] < arr[i])        smallest = l;
    if (r < size && arr[r] < arr[smallest]) smallest = r;
    if (smallest !== i) {
      swap(arr, i, smallest);
      this.heapify(smallest);
    }
  }
 
  
  // to extract the root which is the minimum element
  pop () {
    if (this._size <= 0) return Number.POSITIVE_INFINITY;
    if (this._size == 1) {
      this._size--;
      return this._arr[0];
    }
 
    let arr = this._arr;
    // Store the minimum value, and remove it from heap
    let root = arr[0];
    arr[0] = arr[this._size - 1];
    this._size--;
    this.heapify(0);
    
    return root;
  }
 
  // Decreases key value of key at index i to new_val
  decreaseKey(i, value) {
    let arr = this._arr;
    arr[i] = value;
    while (i != 0 && arr[parent(i)] > arr[i]) {
       swap(arr, i, parent(i));
       i = parent(i);
    }
  }
 
  // Returns the minimum key (key at root) from min heap
  min () { 
    return this._arr[0];
  }
 
  // Deletes a key stored at index i
  // This function deletes key at index i. It first reduced value to minus
  // infinite, then calls extractMin()
  remove (index) {
    this.decreaseKey(index, Number.NEGATIVE_INFINITY);
    this.pop();
  }
 
  // Inserts a new key 'k'
  push (val) {
    // First insert the new key at the end
    this._size++;
    let i   = this._size - 1;
    let arr = this._arr;
    this._arr[i] = val;
 
    // Fix the min heap property if it is violated
    while (i != 0 && arr[parent(i)] > arr[i]) {
      swap(arr, i, parent(i));
      i = parent(i);
    }
  }
  
  empty () {
    return this._size <= 0;
  }
}