BinaryHeap

by evgkch

JavaScript

// Constructor
function BinaryHeap(array){
  this.heap = array || [];
  for (let i = Math.floor(this.heap.length - 1); i >= 0; i--)
    this.constructor.shiftDown(this.heap, i);
};

// Static methods
BinaryHeap.parent = function(i){
  return Math.floor((i-1)/2);
}
BinaryHeap.leftChild = function(i){
  return 2*i+1;
}
BinaryHeap.rightChild = function(i){
  return 2*i+2;
}
// swap two elements of array with indexes i and j
// [1,2] -> [2,1]
BinaryHeap.swap = function(array, a, b){
  var temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}
BinaryHeap.shiftUp = (heap,i)=>{
  while(i >= 0 && heap[BinaryHeap.parent(i)] < heap[i])
  {
    BinaryHeap.swap(heap, BinaryHeap.parent(i), i);
    i = BinaryHeap.parent(i);
  }
};
BinaryHeap.shiftDown = (heap,i)=>{
  let maxIndex = i;
  let l = BinaryHeap.leftChild(i);
  let r = BinaryHeap.rightChild(i);;
  if (l < heap.length && heap[l] > heap[maxIndex])
  {
    maxIndex = l;
    r = BinaryHeap.rightChild(i);
  }
  if (r < heap.length && heap[r] > heap[maxIndex])
  {
    maxIndex = r;
  	l = BinaryHeap.leftChild(i);
  }
  if (i != maxIndex)
  {
    BinaryHeap.swap(heap, i, maxIndex);
    BinaryHeap.shiftDown(heap, maxIndex);
  }
};
  
  // Public methods
  BinaryHeap.prototype.insert = function(p){
  	this.heap.push(p);
    this.constructor.shiftUp(this.heap, this.heap.length - 1);
  };
  BinaryHeap.prototype.extractMax = function(){	
  	const result = this.heap[0];
    this.heap.shift();
    this.constructor.shiftDown(this.heap, 0);
    return result;
  };
  BinaryHeap.prototype.remove = function(i){
  	this.heap[i] = Infinity;
    this.constructor.shiftUp(this.heap, i);
    this.extractMax();
  };
  BinaryHeap.prototype.changePriority = function(i, p){
  	const oldP = this.heap[i];
    if (typeof(oldP) == 'undefined')
    	throw Error(`element with index ${i} is undefined`);
  	this.heap[i] = p;
    if (p > oldP)
    	this.constructor.shiftUp(this.heap, i);
    else
    	this.constructor.shiftDown(this.heap, i);
 ...