Skip to content

Instantly share code, notes, and snippets.

@nehiljain
Created November 21, 2014 03:15
Show Gist options
  • Save nehiljain/ba896164f370339201fc to your computer and use it in GitHub Desktop.
Save nehiljain/ba896164f370339201fc to your computer and use it in GitHub Desktop.
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JS Bin</title>
</head>
<body>
<script id="jsbin-javascript">
function BinaryHeap(scoreFunciton) {
this._content = [];
}
BinaryHeap.prototype = {
push : function (element) {
//if non js code do array resizing if array is full
this._content.push(element);
this.swim(this._content.length - 1);
},
size : function () {
return this._content.length;
},
pop : function () {
//if empty throw error
if ( typeof this._content === 'undefined' ||
this._content.length <= 0) throw new Error('the heap does not exist or is empty');
var result = this._content[0];
// if length is 1 then pop and that is it
this.swap(0, this._content.length - 1);
this._content.pop();
if (this._content.length > 0) {
this.sink(this._content[0]);
}
return result;
},
compare: function (n1,n2) {
var a = this._content[n1];
var b = this._content[n2];
if (typeof a !== 'number') a = Number(a);
if (typeof b !== 'number') b = Number(b);
if (a < b) return -1;
else if ( a == b) return 0;
else return 0;
},
swap : function (n1, n2) {
var temp = this._content[n1];
this._content[n1] = this._content[n2];
this._content[n2] = temp;
},
swim : function (n) {
// should do type checking
while ( n >= 0 && this.compare(n, Math.floor(n/2)) >= 0) {
this.swap(n, Math.floor(n/2));
n = Math.floor(n/2);
}
},
sink : function (n) {
var childIndex;
while ( 2 * n <= this._content.length - 1) {
childIndex = 2 * n;
if ( childIndex < this._content.length && this.compare(childIndex, childIndex + 1) < 0)
childIndex += 1;
this.swap(n, childIndex);
n = childIndex;
}
}
};
</script>
<script id="jsbin-source-javascript" type="text/javascript">function BinaryHeap(scoreFunciton) {
this._content = [];
}
BinaryHeap.prototype = {
push : function (element) {
//if non js code do array resizing if array is full
this._content.push(element);
this.swim(this._content.length - 1);
},
size : function () {
return this._content.length;
},
pop : function () {
//if empty throw error
if ( typeof this._content === 'undefined' ||
this._content.length <= 0) throw new Error('the heap does not exist or is empty');
var result = this._content[0];
// if length is 1 then pop and that is it
this.swap(0, this._content.length - 1);
this._content.pop();
if (this._content.length > 0) {
this.sink(this._content[0]);
}
return result;
},
compare: function (n1,n2) {
var a = this._content[n1];
var b = this._content[n2];
if (typeof a !== 'number') a = Number(a);
if (typeof b !== 'number') b = Number(b);
if (a < b) return -1;
else if ( a == b) return 0;
else return 0;
},
swap : function (n1, n2) {
var temp = this._content[n1];
this._content[n1] = this._content[n2];
this._content[n2] = temp;
},
swim : function (n) {
// should do type checking
while ( n >= 0 && this.compare(n, Math.floor(n/2)) >= 0) {
this.swap(n, Math.floor(n/2));
n = Math.floor(n/2);
}
},
sink : function (n) {
var childIndex;
while ( 2 * n <= this._content.length - 1) {
childIndex = 2 * n;
if ( childIndex < this._content.length && this.compare(childIndex, childIndex + 1) < 0)
childIndex += 1;
this.swap(n, childIndex);
n = childIndex;
}
}
};
</script></body>
</html>
function BinaryHeap(scoreFunciton) {
this._content = [];
}
BinaryHeap.prototype = {
push : function (element) {
//if non js code do array resizing if array is full
this._content.push(element);
this.swim(this._content.length - 1);
},
size : function () {
return this._content.length;
},
pop : function () {
//if empty throw error
if ( typeof this._content === 'undefined' ||
this._content.length <= 0) throw new Error('the heap does not exist or is empty');
var result = this._content[0];
// if length is 1 then pop and that is it
this.swap(0, this._content.length - 1);
this._content.pop();
if (this._content.length > 0) {
this.sink(this._content[0]);
}
return result;
},
compare: function (n1,n2) {
var a = this._content[n1];
var b = this._content[n2];
if (typeof a !== 'number') a = Number(a);
if (typeof b !== 'number') b = Number(b);
if (a < b) return -1;
else if ( a == b) return 0;
else return 0;
},
swap : function (n1, n2) {
var temp = this._content[n1];
this._content[n1] = this._content[n2];
this._content[n2] = temp;
},
swim : function (n) {
// should do type checking
while ( n >= 0 && this.compare(n, Math.floor(n/2)) >= 0) {
this.swap(n, Math.floor(n/2));
n = Math.floor(n/2);
}
},
sink : function (n) {
var childIndex;
while ( 2 * n <= this._content.length - 1) {
childIndex = 2 * n;
if ( childIndex < this._content.length && this.compare(childIndex, childIndex + 1) < 0)
childIndex += 1;
this.swap(n, childIndex);
n = childIndex;
}
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment