JavaScriptでプライオリティーキュー

JavaScriptでアルゴリズム書こうとしたときにプライオリティーキューがないから不便だなと思って書いた。

	var PriorityQueue = function() {
	this.heap = new Array(); //二分木の配列表現
	this.pointer = 0; //最終ノードを表すポインタ
	};
	PriorityQueue.prototype = {
	push : function(x) {
	var i = this.pointer++;
	while (i > 0) {
	//親ノードの番号を求める
	var p = Math.floor((i - 1) / 2);
	//もう逆転してなければ処理を打ち切る
	if (this.heap[p] <= x) break;
	this.heap[i] = this.heap[p];
	i = p;
	}
	this.heap[i] = x;
	},
	pop : function() {
	var ret = this.heap[0];
	var x = this.heap[--this.pointer];
	var i = 0;
	//子ノードがなくなるまでループ
	while (i * 2 + 1 < this.pointer) {
	var a = i * 2 + 1; //左子ノード
	var b = i * 2 + 2; //右子ノード
	if (b < this.pointer && this.heap[b] < this.heap[a]) a = b;
	//もう逆転してなければ処理を打ち切る
	if (this.heap[a] >= x) break;
	this.heap[i] = this.heap[a];
	i = a;
	}
	this.heap[i] = x;
	//最終ノードを削除する
	this.heap.pop();
	return ret;
	},
	size : function() {
	return this.heap.length;
	}
	};
	function test() {
	//テストコード
	var queue = new PriorityQueue();
	queue.push(5);
	queue.push(3);
	queue.push(4);
	queue.push(1);
	queue.push(2);
	alert(queue.size()); // => 5
	alert(queue.pop()); // => 1
	alert(queue.pop()); // => 2
	alert(queue.pop()); // => 3
	alert(queue.size()); // => 2
	queue.push(6);
	alert(queue.size()); // => 3
	alert(queue.pop()); // => 4
	queue.push(2);
	alert(queue.pop()); // => 2
	}

view raw priority_queue.js hosted with ❤ by GitHub

でも書き終わった後にJavaScriptのArrayにはsortメソッドがあることを思い出した。
pushもpopもあるからプライオリティーキューなんかいらんがな。

2012年 ダイジェスト

• 人事異動でメインフレームを扱う部署へ配属になった。
• 格闘技の道場を休会した。
• 初めて学会というものに参加した（発表はしてない）。
• ウェイトとプロテインで体重を10キロ増やした。
• 社会人大学院を修了して修士号（情報科学）を取得した。

修士論文の作成に捧げた一年であった。
今年は色々と生産的な一年にしたいが、さてどうなるものか？

ちなみに新年早々インフルエンザに罹患して寝込んでしまった。
流行には疎いにも関わらず、こういうイヤなところだけ流行に追随する性分らしい。

新年あけましておめでとうございます

遅ればせながら、新年あけましておめでとうございます。
抱えていた個人的なビッグプロジェクトが終了したので、今後はブログのほうもちまちまと更新していきたい。