Javascript Binary Heap

Saturday morning javascript exercise - a binary heap in array and tree implementations. The tree implementation is faster as expected when you shove a lot of data as it as the array implementation must occasionally re-size the backing array. A demo or visualization would be nice but that takes more time than this Saturday morning allows. Code:

	/*
	array implementation of a binary heap, example usage:
	// can optionally provide a comparison function, a function for a max
	// heap is the default if no comparison function is provided
	var bh = binaryHeap();
	bh.push(5);
	bh.push(34);
	bh.push(16);
	var max = bh.pop(); // 34
	print("number in heap: " + bh.size()) // 2
	*/
	var binaryHeap = function(comp) {
	// default to max heap if comparator not provided
	comp = comp || function(a, b) {
	return a > b;
	};
	var arr = [];
	var swap = function(a, b) {
	var temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
	};
	var bubbleDown = function(pos) {
	var left = 2 * pos + 1;
	var right = left + 1;
	var largest = pos;
	if (left < arr.length && comp(arr[left], arr[largest])) {
	largest = left;
	}
	if (right < arr.length && comp(arr[right], arr[largest])) {
	largest = right;
	}
	if (largest != pos) {
	swap(largest, pos);
	bubbleDown(largest);
	}
	};
	var bubbleUp = function(pos) {
	if (pos <= 0) {
	return;
	}
	var parent = Math.floor((pos - 1) / 2);
	if (comp(arr[pos], arr[parent])) {
	swap(pos, parent);
	bubbleUp(parent);
	}
	};
	var that = {};
	that.pop = function() {
	if (arr.length === 0) {
	throw new Error("pop() called on emtpy binary heap");
	}
	var value = arr[0];
	var last = arr.length - 1;
	arr[0] = arr[last];
	arr.length = last;
	if (last > 0) {
	bubbleDown(0);
	}
	return value;
	};
	that.push = function(value) {
	arr.push(value);
	bubbleUp(arr.length - 1);
	};
	that.size = function() {
	return arr.length;
	};
	return that;
	};

view raw gistfile1.js hosted with ❤ by GitHub

	/*
	tree implementation of a binary heap, example usage:
	// can optionally provide a comparison function, a function for a max
	// heap is the default if no comparison function is provided
	var bh = binaryHeap();
	bh.push(5);
	bh.push(34);
	bh.push(16);
	var max = bh.pop(); // 34
	print("number in heap: " + bh.size()) // 2
	*/
	var binaryHeap = function(comp) {
	// default to max heap if comparator not provided
	comp = comp || function(a, b) {
	return a > b;
	};
	var node = function(value, parent, left, right) {
	var that = {};
	that.value = value;
	that.parent = parent;
	that.left = left;
	that.right = right;
	return that;
	};
	var that = {};
	var root = null;
	var last = null;
	var size = 0;
	var bubbleUp = function(node) {
	if (node === root) {
	return;
	}
	if (comp(node.value, node.parent.value)) {
	var temp = node.parent.value;
	node.parent.value = node.value;
	node.value = temp;
	node = node.parent;
	bubbleUp(node);
	}
	};
	var bubbleDown = function(node) {
	if (!node) {
	return;
	}
	var largest = node;
	if (node.left && comp(node.left.value, largest.value)) {
	largest = node.left;
	}
	if (node.right && comp(node.right.value, largest.value)) {
	largest = node.right;
	}
	if (largest !== node) {
	var temp = node.value;
	node.value = largest.value;
	largest.value = temp;
	bubbleDown(largest);
	}
	};
	that.push = function(value) {
	if (!root) {
	root = last = node(value, null, null, null);
	} else if (root === last) {
	root.left = node(value, root, null, null);
	last = root.left;
	} else if (last.parent.left === last) {
	last.parent.right = node(value, last.parent, null, null);
	last = last.parent.right;
	} else {
	var hops = 0;
	var temp = last;
	while (temp.parent && temp.parent.right === temp) {
	temp = temp.parent;
	hops++;
	}
	if (temp !== root) {
	temp = temp.parent.right;
	hops--;
	}
	while (hops-- > 0) {
	temp = temp.left;
	}
	temp.left = node(value, temp, null, null);
	last = temp.left;
	}
	size++;
	bubbleUp(last);
	};
	that.pop = function() {
	if (size === 0) {
	throw new Error("binary heap empty");
	}
	var value = root.value;
	root.value = last.value;
	if (root === last) {
	root = last = null;
	} else if (last.parent.right === last) {
	last.parent.right = null;
	last = last.parent.left;
	} else {
	var hops = 0;
	var temp = last;
	while (temp.parent && temp.parent.left === temp) {
	temp = temp.parent;
	hops++;
	}
	if (temp !== root) {
	temp = temp.parent.left;
	} else {
	hops--;
	}
	while (hops-- > 0) {
	temp = temp.right;
	}
	last.parent.left = null;
	last = temp;
	}
	size--;
	bubbleDown(root);
	return value;
	};
	that.size = function() {
	return size;
	};
	return that;
	};

view raw gistfile1.js hosted with ❤ by GitHub