Created
November 21, 2014 03:15
-
-
Save nehiljain/ba896164f370339201fc to your computer and use it in GitHub Desktop.
// source http://jsbin.com/hetuza
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!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> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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