Implementing a heap in Javascript as part of the Stanford Algorithms course on Coursera

heap.js

// a heap is good at finding min in O(log n) time
// it supports the following methods:
//  - insert
//  - getMin
//  - deleteMin
// it gets initialized with an array
// it stores its data internally as an array, but we visualize it as a binary tree
//       4
//     /   \
//   5     6
//  / \
// 10  9
// each node has from 0-2 children, no more
// the only requirement is each nodes child is less than the parent
// [4, 5, 6, 10, 9]
// to convert index to tree level: if index is even, level = i/2, else level = floor(i/2)
// so level of 6 (index 2) is 2/2 = 1... level of 9 (index 4) is 4/2 = level 2
// in general array element X has children X * 2 and X * 2 + 1

// getting parent: parent of idx 4 = 4/2 = 2 (5) ... parent of idx 5 = floor(5/2) = 2 (5)... parent of idx 2 = 2/2 = 1 (4)

function Heap(data) {
  this.data = [];
  for (var i = 0; i < data.length; i++) {
    this.insert(data[i]);
  }
}

Heap.prototype = {
  insert: function(val) {
    // when inserting you append item, then "bubble it up" to its right spot
    this.data.push(val);
    var childIndex = this.data.length - 1;
    var parentIndex = Math.floor(childIndex/2);
    while (this.data[parentIndex] && this.data[parentIndex] > this.data[childIndex]) {
      // swap child and parent
      var tmp = this.data[parentIndex];
      this.data[parentIndex] = this.data[childIndex];
      this.data[childIndex] = tmp;
      childIndex = parentIndex;
      parentIndex = Math.floor(parentIndex/2);
    } 
  },
  
  getMin: function() {
    // this is just the root
    return this.data[0];
  },
  
  deleteMin: function() {
    // pop the root off, swap last element into its place, then "bubble down"
    var min = this.getMin();
    this.data[0] = this.data.pop();
    var parentIndex = 0;
    var childIndex = 1;
    // the trick here is to swap the smaller of the 2 children up
    if (this.data[childIndex] > this.data[childIndex + 1]) {
      childIndex++;
    }
    while (this.data[childIndex] < this.data[parentIndex]) {
      // swap child up to parent spot
      var tmp = this.data[parentIndex];
      this.data[parentIndex] = this.data[childIndex];
      this.data[childIndex] = tmp;
      childIndex = childIndex * 2;
      parentIndex = Math.floor(childIndex / 2);
      if (this.data[childIndex] > this.data[childIndex + 1]) {
        childIndex++;
      }
    }
  }
}

function main() {
  var heap = new Heap([1]);
  var heapSize = 10000000;
  var sTime = (new Date()).getTime();
  for (var i = 0; i < heapSize; i++) {
    var val = Math.random() * 1000000;
    heap.insert(val);
  }
  console.log('inserted %d vals in %d seconds', heapSize, ((new Date()).getTime() - sTime) / 1000);
  console.log('min is %d', heap.getMin());
  sTime = (new Date()).getTime();
  heap.deleteMin();
  console.log('new min is %d, deleted old min in %d seconds', heap.getMin(), ((new Date()).getTime() - sTime) / 1000);
}

main();