Skip to content

Instantly share code, notes, and snippets.

@basemath

basemath/Heap.js

Last active July 12, 2017 01:12
Show Gist options
  • Save basemath/cee7e8ab7c1b56d3531b299e8c5c59cf to your computer and use it in GitHub Desktop.
Save basemath/cee7e8ab7c1b56d3531b299e8c5c59cf to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Heap.js
/**
* A simple Binary Heap implementation for JS
* https://en.wikipedia.org/wiki/Binary_heap
*
* Useful improvements would support a comparsion function
* and allow object removal by reference.
*/
function Heap () {
var _arr = [];
// === Private ================================= //
function childIndicesOf (n) {
return [((2 * n) + 1), ((2 * n) + 2)];
}
function favoredChildIndexOf (n) {
var childAIndex = (2 * n) + 1;
var childBIndex = (2 * n) + 2;
return (_arr[childAIndex] > _arr[childBIndex]) ? childAIndex : childBIndex;
}
function parentIndexOf (n) {
return Math.floor((n - 1) / 2);
}
function bubble (n) {
var item = _arr[n];
var parentIndex = parentIndexOf(n);
var parent = _arr[parentIndex];
if (item > parent) {
_arr[n] = parent;
_arr[parentIndex] = item;
bubble(parentIndex);
return true;
}
return false;
}
function sink (n) {
var item = _arr[n];
var favoredChildIndex = favoredChildIndexOf(n);
var favoredChild = _arr[favoredChildIndex];
if (item < favoredChild) {
_arr[n] = favoredChild;
_arr[favoredChildIndex] = item;
sink(favoredChildIndex);
return true;
}
return false;
}
// === Public ================================== //
this.insert = function (item) {
_arr.push(item);
bubble(_arr.length - 1);
}
this.removeAt = function (n) {
if (n === _arr.length - 1) {
_arr.pop();
} else {
_arr[n] = _arr.pop();
bubble(n) || sink(n);
}
}
this.peek = function () {
return _arr[0];
}
this.pop = function () {
var root = _arr[0];
this.removeAt(0);
return root;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment