週刊 spaghetti_source

Randomized Meldable Heap

09:26

// Randomized Meldable Heap
// - merge : merge two heaps
// - push  : insert element to the heap
// - pop   : delete minimum element in the heap
// - top   : return minimum element in the heap
const int MAXSIZE = 10100200;
int N = 1;
int key[MAXSIZE];
int ch[2][MAXSIZE];
int merge(int i, int j) {
  if (!i || !j) return i ? i : j;
  if (key[i] > key[j]) swap(i, j);
  int b = rand() % 2;
  ch[b][i] = merge(ch[b][i], j);
  return i;
}
int push(int i, int k) { return merge(i, newnode(k)); }
int pop(int i) { return merge(ch[0][i], ch[1][i]); }
int top(int i) { return key[i]; }

2つのヒープ構造をマージする際，左右どちらにマージするかをランダムに決定するだけでmergeの期待計算量がO(log n)になる．

証明．

マージ接点の動きは木の上のランダムウォークになるから，その期待歩数がO(log n)であることを示せば十分．期待歩数をf(n)とするとf(n) = 1 + f(n1)/2 + f(n2)/2となる．ただしn1とn2は左右の子の数．n未満のmについてf(m)≦c log mを仮定する．c も十分大きいものとしておく．すると f(n) ≦ 1 + c/2 ( log(n1) + log(n2) ) となる．右辺を 1 + n1 + n2 = n の条件で最大化する．logは凹関数なので真ん中付近を取るのがベスト．n1 = n2 = 1/2 を代入して f(n) ≦ 1 + c log(n) - c ≦ c log(n)．

実時間比較

比較対象はskew heap, randomized heap, std::priority_queue, std::multiset．

skew heapとrandomized heapはどちらもmerge操作を基本とするmeldable heapだから，ど正面からの競合相手．priority_queueとmultisetはmeldableでないので競合相手でないが，リファレンスとして．

実験に用いたインスタンスは5例で，サイズはn = 10,000,000．

言語はC++(G++4.3.3)で，コンパイルオプションは -O2．

-	skew heap	rand heap	pqueue	multiset
ランダム	28.41	34.05	3.31	17.47
単調増加	13.85	26.16	1.28	5.44
単調減少	0.22	0.28	1.12	5.21
増加後減少	12.70	23.35	1.51	4.56
減少後増加	5.96	11.28	1.36	4.57

結論：rand heapはskew heapに2倍程度劣る（時間差はおおむねrand()関数の呼び出しの時間）．とはいえ高々2倍なのでskew heapの回転方向を忘れちゃったテヘペロなときは有力な選択肢かもしれない・・・？

お久しぶりです

09:21

環境も変わったので，少しずつ再開していきます．