Skip to content

Instantly share code, notes, and snippets.

@badmonster0
Last active December 10, 2015 04:49
Show Gist options
  • Save badmonster0/5e8e6e204bbe45587c62 to your computer and use it in GitHub Desktop.
Save badmonster0/5e8e6e204bbe45587c62 to your computer and use it in GitHub Desktop.
Simple Heap Impl. Support add, pop and print. Support Max heap and min heap
var Heap = function(type){
this.heap = []
this.type = type || "MAX";
}
Heap.prototype.print = function(){
var r;
if (this.type == "MIN"){
r = []
for (var i = 0; i< this.heap.length; i++){
r.push(-this.heap[i])
}
}else{
r = this.heap
}
console.log(r)
}
// 0,1, 2,3,4 i*2 +1, i*2 +2
// bigger elem on top
Heap.prototype.add = function(x){
if (this.type == "MIN"){
x = -x;
}
this.heap.push(x);
var i = this.heap.length -1;
while (i>0){
var p = Math.floor((i - 1)/2)
if (this.heap[i] < this.heap[p]){
break;
}else{
var tmp = this.heap[i];
this.heap[i] = this.heap[p];
this.heap[p] = tmp;
i = p;
}
}
}
Heap.prototype.pop = function(){
var omax = this.heap[0]//original max;
this.heap[0] = this.heap.pop();
var i = 0;
while (true){
console.log('i', i)
var c1 = i*2 + 1;
var c2 = i*2 + 2;
iv = this.heap[i] //ivalue
c1v = this.heap[c1]//c2value
c2v = this.heap[c2]//c1value
var bigger;
if ((iv >= c1v && iv >= c2v) || (iv > c1v&& c2v == null) || (c1v ==null && c2v ==null)){
break;
}
// if (iv <)
if (iv < c1v){
bigger = c1;
}
if (c2v!=null && iv < c2v){
bigger = c2;
}
this.heap[i] = this.heap[bigger];
this.heap[bigger] = iv;
i = bigger;
}
if (this.type == "MIN"){
omax = -omax;
}
return omax;
}
var heap = new Heap('MIN');
heap.add(1)
heap.add(2)
//heap.pop()
heap.print()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment