Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
/*
* 優先度付待ち行列
*
* 値を半順序集合とし、根に近いほど値が小さくなるような二分木を構成する.
* 今回は単純に値を演算(<), (>)で比較している.数値くらいであることを前提にしてる.
* 構造を保ちつつ、待ち行列に値を加える#addと最小要素を取り出す#popを実装した.
* #addは単純.#popが手こずった
*
* #isLeafとか#child_countとかは必要を感じて後から作ったから
* それよりも前で使うべき箇所があったかもしれない
*/
function Tree(val,a,b) {
/*
* new Tree(val [,left [,right]])
* := a node has val with left (and right) as children or no child
* child being undefined behaves just a Leaf
*/
this.val = val;
this.left = a;
this.right = b;
}
tp = Tree.prototype;
tp.print = function() { // for debug
function print_sub(t) {
if (t == undefined || t.val == undefined) return "(Leaf)";
else return "(" + t.val + " " + print_sub(t.left) + " " + print_sub(t.right) + ")";
}
var str = print_sub(this, 0);
console.log(str);
}
tp.isLeaf = function() {
return (this.left == undefined && this.right == undefined) || this.val == undefined;
}
tp.child_count = function() {
return (this.left == undefined ? 0 : 1) + (this.right == undefined ? 0 : 1);
}
tp.add = function(val) {
/*
* 一旦木の一番下につけて、順序が保たれるまでノードの値を交換する.
* add_at_last()では一番下まで辿って値を追加するが、その
* 辿ったルートをrouteに記憶しておき、swap_until()で使う.
*/
if (this.val == undefined) {
this.val = val;
return this;
}
var route = [];
function add_at_last(t) {
route.push(t);
if (t.val == undefined) { t.val = val; }
else if (t.left == undefined) { t.left = new Tree(val); route.push(t.left); }
else if (t.right == undefined) { t.right = new Tree(val); route.push(t.right); }
else {
add_at_last(Math.random() < .5 ? t.left : t.right);
// ズルい
}
}
add_at_last(this);
function swap_until() {
if (route.length < 2) return;
var child = route.pop(),
par = route.pop();
if (child.val < par.val) {
var c = child.val;
child.val = par.val;
par.val = c;
route.push(par);
swap_until();
}
}
swap_until();
return this;
}
tp.pop = function() {
/*
* 最小要素、即ち根の値を取り出す.
* 取り出すとは値を返すことと、それを持っていた節を削除した
* ような木に構成しなおすこと
* 根が最小要素を持つので、その値を返す為に覚えておいて削除する.
* 空になった根には末葉から持ってきたものを埋め、
* (単に根の値を上書きするだけで良いが)
* 最後に値の逆転が治るまで交換を繰り返す
*/
var ret = this.val;
if (this.isLeaf()) {
this.val = undefined;
return ret;
}
function remove_last(t) {
if (t.left != undefined && t.left.isLeaf()) {
var val = t.left.val;
t.left = undefined; // remove. wait for garbage collect
return val;
}
else if (t.right != undefined && t.right.isLeaf()) {
var val = t.right.val;
t.right = undefined;
return val;
}
else {
return t.right == undefined ? remove_last(t.left) :
t.left == undefined ? remove_last(t.right) :
Math.random() < .5 ? remove_last(t.left) :
remove_last(t.right);
}
}
this.val = remove_last(this);
function swap_until(t) {
if (t == undefined || t.isLeaf()) return;
if (t.child_count() == 2) {
var v1 = t.left.val,
v2 = t.right.val,
vl = t.val;
if (v1 < v2) {
t.val = v1;
t.left.val = vl;
swap_until(t.left);
} else {
t.val = v2;
t.right.val = vl;
swap_until(t.right);
}
} else {
var child = t.right == undefined ? t.left : t.right;
if (t.val > child.val) {
var cv = child.val;
child.val = t.val;
t.val = cv;
swap_until(child);
}
}
}
swap_until(this);
return ret;
}
// sample code
var a = new Tree();
a.add(10);
a.add(20);
a.add(30);
a.print();
a.add(15)
.add(35)
.add(25)
.print();
console.log(a.pop() + " was popped.");
a.print();
var b = new Tree(1, new Tree(2, new Tree(3)), new Tree(4));
b.print();
console.log(b.pop() + " was popped.");
console.log(b.pop() + " was popped.");
console.log(b.pop() + " was popped.");
console.log(b.pop() + " was popped.");
b.print();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment