AMD module for binary heaps. Supports heapify, merge, insert, extract, remove (given an offset), decrease/increase key, and custom sorting functions.

Heap.js

define(
	'Heap',
	function() {
		function Heap(array, fn) {
			var instance = Object.create(Heap.prototype);

			instance._sortFn = typeof fn === 'function' ? fn : Heap.defaultSort;
			instance._store = Array.isArray(array) ? array : [];

			Heap.heapify(instance._store, instance._sortFn);

			return instance;
		}

		Heap.defaultSort = function(a, b) {
			if (a < b) return -1;
			if (a > b) return 1;
			return 0;
		};

		Heap.heapify = function(array, fn) {
			var i;

			fn = typeof fn === 'function' ? fn : Heap.defaultSort;

			if (array.length) {
				if (typeof array.explicitKey === 'undefined') {
					array.explicitKey = typeof array[0] !== 'number';
				}

				for (i = Math.floor(array.length / 2) + 1; i > 0; i--) {
					bubbleUp(array, fn, i);
				}
			}

			return array;
		};

		Heap.merge = function(a, b) {
			var heap = Heap(a._store.slice(0), a._sortFn);
			return heap.merge(b);
		};

		Heap.prototype = {
			merge: function(heap) {
				var store = this._store.concat(heap._store);
				Heap.heapify(store, this._sortFn);
				
				this._store = store;

				return this;
			},

			insert: function(key, item) {
				if (typeof this._store.explicitKey === 'undefined') {
					this._store.explicitKey = typeof item !== 'undefined';
				}

				bubbleUp(
					this._store,
					this._sortFn,
					this._store.push(this._store.explicitKey ? { key: key, value: item } : key) - 1
				);
			},

			promoteKey: function(key, item) {
				var i;

				for (i = 0; i < this._store.length; i++) {
					if (item === (this._store[i].value || this._store[i])) {
						if (this._store.explicitKey) {
							this._store[i].key = key;
						} else {
							this._store[i] = key;
						}
						bubbleUp(this._store, this._sortFn, i);
						break;
					}
				}
			},

			extract: function() {
				return this.removeAt(0);
			},

			removeAt: function(pos) {
				var removedItem;

				swap(this._store, pos, this._store.length - 1);
				removedItem = this._store.pop();
				percolateDown(this._store, this._sortFn, 0);

				return removedItem.value || removedItem;
			},

			peek: function() {
				return this._store[0];
			},

			size: function() {
				return this._store.length;
			},

			isEmpty: function() {
				return !this.size();
			}
		};

		// Alias methods
		Heap.prototype.push = Heap.prototype.insert;
		Heap.prototype.pop = Heap.prototype.extract;
		Heap.prototype.decreaseKey = Heap.prototype.increaseKey = Heap.prototype.promoteKey;


		// Helper methods
		function getParent(k) {
			return Math.floor((k - 1) / 2);
		}

		function getLeftChild(k) {
			return k * 2 + 1;
		}

		function getRightChild(k) {
			// Right child is just after left child
			return getLeftChild(k) + 1;
		}

		function swap(array, i, j) {
			var temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}


		function sortKeys(array, fn, a, b) {
			a = array[a];
			b = array[b];
			if (array.explicitKey) {
				a = a.key;
				b = b.key;
			}
			return fn(a, b);
		}

		function bubbleUp(array, fn, pos) {
			var parent = getParent(pos);

			while (pos > 0 && sortKeys(array, fn, pos, parent) < 0) {
				swap(array, pos, parent);
				pos = parent;
				parent = getParent(pos);
			}
		}

		function percolateDown(array, fn, pos) {
			var len = array.length,
				leftChild,
				rightChild,
				swapChild;

			while ((leftChild = getLeftChild(pos)) < len) {
				swapChild = leftChild;
				rightChild = leftChild + 1;

				if (rightChild < len &&
					sortKeys(array, fn, rightChild, leftChild) < 0) {
					swapChild = rightChild;
				}

				if (sortKeys(array, fn, pos, swapChild) > 0) {
					swap(array, pos, swapChild);
					pos = swapChild;
				} else {
					pos = len;
				}
			}
		}

		return Heap;
	}
);