heap.js

function aStar_compare(a, b) {
	return a.cost + a.estimate < b.cost + b.estimate || (a.cost + a.estimate == b.cost + b.estimate && a.cost < b.cost);
}

var Heap = function(compare) {
	if (!compare) {
		compare = function(a, b) {return a < b;};
	}
	this.compare = compare;
	this.heap = [];

}

Heap.prototype.push = function(obj) {
	this.heap.push(obj);
	this._siftdown(0, this.heap.length - 1);
};

Heap.prototype.pop = function() {
	var last_element = this.heap.pop();
	if (this.heap.length) {
		var result = this.heap[0];
		this.heap[0] = last_element;
		this._siftup(0);
		return result;
	} else {
		return last_element;
	}
};

Heap.prototype._siftdown = function(start, pos) {
	var new_item = this.heap[pos];
	while (pos > start) {
		var parent_pos = (pos - 1) >> 1;
		var parent = this.heap[parent_pos];
		if (this.compare(new_item, parent)) {
			this.heap[pos] = parent;
			pos = parent_pos;
		} else {
			break;
		}
	}
	this.heap[pos] = new_item;
};

Heap.prototype._siftup = function(pos) {
	var end_pos = this.heap.length;
	var start_pos = pos;
	var new_item = this.heap[pos];
	var child_pos = (pos << 1) + 1;
	while (child_pos < end_pos) {
		var right_pos = child_pos + 1;
		if (right_pos < end_pos && !this.compare(this.heap[child_pos], this.heap[right_pos])) {
			child_pos = right_pos; 
		}
		this.heap[pos] = this.heap[child_pos];
		pos = child_pos;
		child_pos = (pos << 1) + 1;

	}
	this.heap[pos] = new_item;
	this._siftdown(start_pos, pos);
};