12 Implementation of Heap in JavaScript

heap.js

class Heap {
  constructor() {
    /* A heap is a tree-based data structure with the following features
       - Child nodes for a node in the heap is always greater(or smaller) than
         the parent node(which can be categorized as min-heap or nax-heap)
       - A heap is a complete tree. Because of this feature, we can keep records
         of a heap by array and refer to all nodes by index manipulation
       - For example, in the case of a binary heap where a node has an index of 
         i, then its children indexes should be ((i + 1) << 1) - 1 and
         (i + 1) << 1
       - Below is an implementation of binary-max-heap */

    // Use an array to keep record of the heap
    this.list = [];
  }

  // Add one node to the heap
  add(n) {
    this.list.push(n);
    this.siftUp(this.list.length - 1);
  }

  // Add multiple nodes to the heap(aka building a heap with an array)
  addAll(arr) {
    for (var i = 0; i < arr.length; i++) {
      this.add(arr[i]);
      this.siftUp(this.list.length - 1);
    }
  }

  /* After adding the node to the end of the heap, we should swap the node with
     its parent node recursively to maintain the max-heap */
  siftUp(fromIndex) {
    if (fromIndex == 0) {
      return;
    } else {
      var child = this.list[fromIndex];
      var parentIndex = this.getParentIndex(fromIndex);
      var parent = this.list[parentIndex];
      if (parent && child > parent) {
        this.swap(this.list, fromIndex, parentIndex);
      }
      this.siftUp(parentIndex);
    }
  }

  getParentIndex(i) {
    var result;
    if (i == 0) {
      result = null;
    } else {
      result = ((i + 1) >> 1) - 1;
    }
    return result;
  }

  swap(arr, a, b) {
    var t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
  }

  /* The root node of a binary-max-heap always contains the max value.
     Extract it to get the max value */
  extract() {
    var max = this.list.shift();
    var last = this.list.pop();

    // move the last node to the frontmost
    this.list.unshift(last);

    // and swap recursively with either of the child node to maintain the max-heap
    this.siftDown(0);
    return max;
  }

  siftDown(fromIndex) {
    var childrenIndexes = this.getChildrenIndexes(fromIndex);
    var a = childrenIndexes[0];
    var b = childrenIndexes[1];
    var leftChild = this.list[a];
    var rightChild = this.list[b];
    var parent = this.list[fromIndex];
    if (!leftChild && !rightChild) {
      return;
    } else if (leftChild && !rightChild) {
      if (leftChild > parent) {
        this.swap(this.list, fromIndex, a);
        this.siftDown(a);
      }
    } else if (!leftChild && rightChild) {
      if (rightChild > parent) {
        this.swap(this.list, fromIndex, b);
        this.siftDown(b);
      }
    } else if (leftChild && rightChild) {
      if (leftChild > rightChild && leftChild > parent) {
        this.swap(this.list, fromIndex, a);
        this.siftDown(a);
      } else if (rightChild > leftChild && rightChild > parent) {
        this.swap(this.list, fromIndex, b);
        this.siftDown(b);
      }
    }
  }

  getChildrenIndexes(i) {
    var k = (i + 1) << 1;
    var x = k - 1;
    var y = k;
    if (x > this.list.length) {
      x = null;
    }
    if (y > this.list.length) {
      y = null;
    }
    return [x, y];
  }

  // Implementation of heap sort: by invoking extract() recursively
  sort(){
    var result = [];
    var max;
    while((max = this.extract()) !== undefined){
      // this will get an incremental sorted result
      result.unshift(max);
      // this will get an decremental sorted result
      // result.push(max);
    }
    return result;
  }
}

var arr = [1,5,4,6,7,9,8,2,3,0];
var heap = new Heap();
heap.addAll(arr);
console.log(heap.sort()); // [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]