priority_queue.js

/**
 * Priority Queue for JavaScript
 * 
 * simple implementation of priority queue with heap on javascript.
 * 
 */

var PriorityQueue = function(cmp){
  this.heap = [];
	this.cmp = (cmp == null) ? PriorityQueue.CMP : cmp;
};

PriorityQueue.prototype.push = function(v){
	var k, p, t;
	k = this.heap.length;
	this.heap.push(v);
	while(k > 0){
		p = (k - 1) >> 1;
		if(this.cmp(this.heap[k], this.heap[p]) < 0){
			t = this.heap[p];
			this.heap[p] = this.heap[k];
			this.heap[k] = t;
			k = p;
		}else{
			break;
		}
	}
};

PriorityQueue.prototype.pop = function(){
	if(this.heap.length == 1) return this.heap.pop();
	var ret = this.heap[0], k, len, a, b, c, t;
	this.heap[0] = this.heap.pop();
	len = this.heap.length;
	k = 0;
	for(;;){
		a = (k << 1) + 1, b = (k << 1) + 2;
		if(a >= len) break;
		c = (b < len && this.cmp(this.heap[b], this.heap[a]) < 0) ? b : a;
		if(this.cmp(this.heap[c], this.heap[k]) < 0){
			t = this.heap[c];
			this.heap[c] = this.heap[k];
			this.heap[k] = t;
			k = c;
		}else{
			break;
		}
	}
	return ret;
};

PriorityQueue.prototype.top = function(){
	return this.heap[0];
};

PriorityQueue.prototype.empty = function(){
	return this.heap.length == 0;
};

PriorityQueue.prototype.size = function(){
	return this.heap.length;
};

PriorityQueue.prototype.clear = function(){
	this.heap.length = 0;
};

PriorityQueue.CMP = function(a, b){ return a - b;};

if(require.main === module){
	/* Test with heap sort */
    var a = [], e = [], i, exp;
	var N = 100000;
	for(i = 0; i < N; i++){
		a.push(Math.random());
		e.push(a[i]);
	}
	e.sort(function(a, b){ return a - b; });
	var pq = new PriorityQueue();
	console.assert(pq.empty(),
				   'Priority Queue must be empty');
	console.assert(pq.size() == 0,
				   'Priority Queue size must be zero');
	for(i = 0; i < N; i++){
		pq.push(a[i]);
	}
	for(i = 0; i < N; i++){
		console.assert(!pq.empty(),
					   'Priority Queue must not be empty');
		console.assert(pq.size() == N - i,
					   'Priority Queue size must be', N - i,
					   'but', pq.size());
		exp = pq.top();
		a[i] = pq.pop();
		console.assert(exp == a[i], 
					   'Priority Queue top must equal result of pop', a[i],
					   'but', exp);
	}
	console.assert(pq.empty(),
				   'Priority Queue must be empty');
	console.assert(pq.size() == 0,
				   'Priority Queue size must be', 0,
				   'but', pq.size());
	for(i = 0; i < N; i++){
		if(a[i] != e[i]) console.assert(a[i] == e[i],
										'sort result missmatch: ',
									   a[i], 'and', e[i]);
	}

	e.sort(function(a, b){ return b - a; });
	pq = new PriorityQueue(function(a, b){ return b - a; });
	console.assert(pq.empty(),
				   'Priority Queue must be empty');
	console.assert(pq.size() == 0,
				   'Priority Queue size must be zero');
	for(i = 0; i < N; i++){
		pq.push(a[i]);
	}
	for(i = 0; i < N; i++){
		console.assert(!pq.empty(),
					   'Priority Queue must not be empty');
		console.assert(pq.size() == N - i,
					   'Priority Queue size must be', N - i,
					   'but', pq.size());
		exp = pq.top();
		a[i] = pq.pop();
		console.assert(exp == a[i], 
					   'Priority Queue top must equal result of pop', a[i],
					   'but', exp);
	}
	console.assert(pq.empty(),
				   'Priority Queue must be empty');
	console.assert(pq.size() == 0,
				   'Priority Queue size must be', 0,
				   'but', pq.size());
	for(i = 0; i < N; i++){
		if(a[i] != e[i]) console.assert(a[i] == e[i],
										'sort result missmatch: ',
									   a[i], 'and', e[i]);
	}

	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.clear();
	console.assert(pq.empty(),
				   'Priority Queue must be empty');
	console.assert(pq.size() == 0,
				   'Priority Queue size must be', 0,
				   'but', pq.size());
}