Heap

gistfile1.js

var Heap = (function(){
  function otheri(index, level_offset){
    var level = Math.floor(Math.log2(index+1));
    var level_start = Math.pow(2, level) - 1;
    var offset = index - level_start;
    var other_level_start = Math.pow(2, level + level_offset) -1;
    var other_offset = Math.floor(offset * Math.pow(2, level_offset));
    return other_level_start + other_offset;
  };
  
  function parenti(index){
    return otheri(index, -1);
  };

  function childreni(index){
    return otheri(index, 1);
  };

  function Heap(comparison){
    if(comparison){
      this.comparison = comparison;
    }
    this._data = []
  };

  Heap.prototype.comparison = function(a, b){ return a >b;};

  Heap.prototype.sift_up = function(index){
    var parent = parenti(index);
    if(parent < 0){
      return;
    }

    if(! this.comparison(this._data[index], this._data[parent])){
      var temp = this._data[index];
      this._data[index] = this._data[parent];
      this._data[parent] = temp;
      if(index != 0){
        this.sift_up(parent);
      }
    }
  };

  Heap.prototype.sift_down = function(index){
    var child_left_i = childreni(index);
    var child_right_i = child_left_i + 1;
    if(child_left_i >= this._data.length){
      return;
    }
    if(child_right_i > this._data.length){
      var smallest_child = child_left_i;
      var leaf = true;
    }
    else{
      var leaf = false;
      if(!this.comparison(this._data[child_left_i], this._data[child_right_i])){
        var smallest_child = child_left_i;
      }
      else{
        var smallest_child = child_right_i;
      }
    }

    if(!this.comparison(this._data[smallest_child], this._data[index])){
      var temp = this._data[index];
      this._data[index] = this._data[smallest_child];
      this._data[smallest_child] = temp;
      this.sift_down(smallest_child);
    }
  };

  Heap.prototype.push = function push(item){
    var new_index = this._data.length;
    this._data[new_index] = item;
    this.sift_up(new_index);
    return item;
  };

  Heap.prototype.peek = function peek(){
    return this._data[0];
  }

  Heap.prototype.pop = function pop(){
    var result = this._data[0];
    this._data[0] = this._data[this._data.length - 1];
    this.sift_down(0);
    this._data.pop()
    return result;
  };

  return Heap;
})();