Created
April 3, 2016 03:04
Star
You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 優先度付待ち行列 | |
* | |
* 値を半順序集合とし、根に近いほど値が小さくなるような二分木を構成する. | |
* 今回は単純に値を演算(<), (>)で比較している.数値くらいであることを前提にしてる. | |
* 構造を保ちつつ、待ち行列に値を加える#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