Skip to content

Instantly share code, notes, and snippets.

@liamgriffiths
Last active January 1, 2016 22:59
Show Gist options
  • Save liamgriffiths/8213560 to your computer and use it in GitHub Desktop.
Save liamgriffiths/8213560 to your computer and use it in GitHub Desktop.
binary heap and priority queue structures
/*
* Binary Heap
*
* This is a heap which is built on top of a binary tree. The binary tree can
* be built using a regular array and some arithmetic to find the array indicies
* of a particular node's children.
*
* The Binary Heap is a 'complete tree', meaning that all levels of the tree are
* completely filled before going deeper. The levels of the tree are filled from
* left to right.
*
* The Binary Heap is also satisfies the 'heap property', that is, it is heap
* ordered - which means that every node is either always greater or less than
* its children. One could implement a 'binary-min' tree which which would mean
* that all nodes are less than or equal to their children. Or conversely a
* 'binary-max' tree would mean that all nodes are greater than or equal to
* their children.
*
* What is this good for:
* - Implementing Priority Queues
*
* References:
* http://eloquentjavascript.net/appendix2.html
* http://opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html
* http://en.wikipedia.org/wiki/Binary_heap
*/
function BinaryHeap(_compareFn) {
// nodes are stored in a regular array
this.nodes = [];
// compare the values of two nodes at indexA and indexB
this.compareFn = _compareFn || function(nodeA, nodeB) {
if(nodeA > nodeB) return 1;
if(nodeA < nodeB) return -1;
return 0;
};
}
/**
* Lookup left child index
* @param {Number} i - parent index
* @returns {Number} - index for left child node
*/
BinaryHeap.prototype.left = function(i) {
return 2 * i + 1;
};
/**
* Lookup right child index
* @param {Number} i - parent index
* @returns {Number} - index for right child node
*/
BinaryHeap.prototype.right = function(i) {
return 2 * i + 2;
};
/**
* Lookup parent node index
* @param {Number} i - child index
* @returns {Number} - index for parent node
*/
BinaryHeap.prototype.parent = function(i) {
return Math.floor((i - 1) / 2);
};
/**
* Insert new node to heap. Add to the end of the array then "bubble up"
* @param {Object} node - object to serve as node
* @returns {BinaryHeap} this
*/
BinaryHeap.prototype.add = function(node) {
this.nodes.push(node); // add node to the end of the array
this.bubbleUp(this.nodes.length - 1);
return this;
};
/**
* Swap two nodes in the heap at indexA and indexB
* @param {Number} indexA
* @param {Number} indexB
* @returns {BinaryHeap} this
*/
BinaryHeap.prototype.swapNodes = function(indexA, indexB) {
var nodeA = this.nodes[indexA];
var nodeB = this.nodes[indexB];
this.nodes[indexA] = nodeB;
this.nodes[indexB] = nodeA;
return this;
};
/**
* Reorders the nodes in the heap to ensure that the node at index i is less
* than its parents value. This is done by comparing the last node of the heap
* with its parents and swapping it until it is not less than its parent.
* @param {Number} i - index of the node to bubble up
* @returns {BinaryHeap} this
*/
BinaryHeap.prototype.bubbleUp = function(i) {
pi = this.parent(i);
// loop until node at index i is <= it's parent node
while(this.compare(i, pi) < 0){
this.swapNodes(i, pi);
i = pi;
pi = this.parent(i);
}
return this;
};
/**
* Returns the first node in the heap. This will be the smallest value node in
* the heap. Resort the array by "bubbling down" to make sure the first node in
* the heap is again the smallest value.
* @returns {Object} - node
*/
BinaryHeap.prototype.remove = function() {
var rootNode = this.nodes.shift();
this.bubbleDown();
return rootNode;
};
/**
* Apply this.compareFn to nodes at indexA and indexB
* @param {Number} indexA
* @param {Number} indexB
* @returns {Number} - result of comparision function (-1, 0, 1)
*/
BinaryHeap.prototype.compare = function(indexA, indexB) {
var nodeA = this.nodes[indexA];
var nodeB = this.nodes[indexB];
return this.compareFn(nodeA, nodeB);
};
/**
* Reorder the heap. This is done by taking the last node on the heap
* and putting it at the front, then push it through the array swapping with
* greater values until it is less than its parents.
* @returns {BinaryHeap} this
*/
BinaryHeap.prototype.bubbleDown = function() {
if(this.size() < 1) return; //
// take last node in array off and put at the front of the array
var lastNode = this.nodes.pop();
this.nodes.unshift(lastNode);
var i = 0;
var l = this.left(0); // left child index
var r = this.right(0); // right child index
// while the current node's value is greater than its children
while(this.compare(i, l) > 0 || this.compare(i, r) > 0){
if(this.compare(l, r) < 0){
// left child is less than right
this.swapNodes(i, l);
i = l;
}else{
// right child is less than left
this.swapNodes(i, r);
i = r;
}
l = this.left(i);
r = this.right(i);
}
return this;
};
/**
* Size of the heap.
* @returns {Number} - count of the nodes in the heap
*/
BinaryHeap.prototype.size = function() {
return this.nodes.length;
};
module.exports = BinaryHeap;
/*
* Priority Queue
*
* Similar to an ordinary FIFO queue, but each element in the queue can be
* assigned a priority which determines the queue's ordering. The PQ is typiclly
* built on top of a Binary Heap (as it is here) because it can guarantee that
* the first element to be pulled off the queue will be of the highest priority
* and is fast at achieving this ordering.
*
* Note: because this PQ is built on a BinaryHeap an important part of this
* implementation is that we must provide the BinaryHeap with a sort function
* that knows how to compare the elements we are adding to the queue.
*
* What this is good for:
* - Can be used to sort elements by priority value
* - Scheduling events
* -
*
* References:
* http://en.wikipedia.org/wiki/Priority_queue
*/
var BinaryHeap = require('./BinaryHeap');
function PriorityQueue() {
var compareFn = function(nodeA, nodeB) {
if (nodeA && nodeB) {
if (nodeA.priority > nodeB.priority) return 1;
if (nodeA.priority < nodeB.priority) return -1;
}
return 0;
};
this.queue = new BinaryHeap(compareFn);
}
/**
* Add an element to the queue with a priority.
* @param {*} element - something to queue
* @param {Number} priority
* @returns {PriorityQueue} this
*/
PriorityQueue.prototype.enqueue = function(element, priority) {
this.queue.add({element: element, priority: priority});
return this;
};
/**
* Remove element with highest priority from the queue.
* @returns {*|undefined} - element || undefined if queue is empty.
*/
PriorityQueue.prototype.dequeue = function() {
if (this.isEmpty()) {
return undefined;
} else {
var highestPriority = this.queue.remove();
return highestPriority.element;
}
};
/**
* Check whether the queue is empty.
* @returns {Boolean}
*/
PriorityQueue.prototype.isEmpty = function(){
return this.queue.length === 0;
};
/**
* Get size of the queue.
* @returns {Number}
*/
PriorityQueue.prototype.size = function(){
return this.queue.size();
};
module.exports = PriorityQueue;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment