週刊 spaghetti_source

Pairing Heap

11:35

マージ可能ヒープの中で，現在「実用的に最速」と言われているものが Pairing heap です．

マージ可能ヒープなら，実装量的にはSkew Heapや乱択ヒープが非常に短いし，ヒープを取り替えたらTLEがACになるようなことはめったにないので，競技プログラミング的には微妙なネタですが，競技に直接使えるメジャーテクニックなんてだいたい語り尽くされているので，ここではそんなことは気にせずにやっていきます．

歴史的背景

Pairing Heap提案の2年前，Fredman-Tarjan(1984) がFibonacci Heapを提案しました．これにより最短路やらなんやらの計算量が全部落ちて凄い，という盛り上がりが起きたのですが，すぐに実用的には使えないと言われてしまいます（提案してすぐに「実用的には使えない」と言われるのはとんでもないことで，どれだけFibonacci Heapに注目が集まったかを表しています）．

一方，ほぼ同時期にSleator-Tarjan(1985) がLink Cut Treeの実装として，自己組織化平衡二分探索木のSplay Treeを提案しました．これは（当時知られていた）平衡木よりもずっとシンプルで，しかも実用的にも十分早いというものでした．

そこで，この２つのアイデアを組み合わせてFibonacci Heapを自己組織化版にする，という発想で作られたのが，Fredman-Sedgewick-Sleator-Tarjan(1986)のPairing Heapです．自己組織化アルゴリズムは実装がシンプルなわりに実用的に早いので，Fibonacci Heapの木の形状をamortizedで達成できれば実用的により高速になるだろうという発想です．

実装

コードを見ながら説明したほうがよいので，まずはコードを示します．Haskellにて．

data Heap a = Empty | Node a [Heap a] deriving (Show, Eq)

merge Empty h = h
merge h Empty = h
merge (Node x xs) (Node y ys)
  | x < y     = Node x (Node y ys : xs)
  | otherwise = Node y (Node x xs : ys)

mergeList []       = Empty
mergeList [x]      = x
mergeList (x:y:xs) = merge (merge x y) (mergeList xs)

push x h = merge (Node x []) h

pop (Node x xs) = mergeList xs

top (Node x xs) = x

ヒープのデータ構造は，各ノードがキーと子のリストをもつ可変長多分木で実装します．Binomial Heapの系列ですね．

マージ可能ヒープの基本は「mergeを作って，他の操作はmergeで実装」なので，Pairing Heapもそれに準じますが，木と木のmergeと，リストのmergeを区別します．木同士のmergeをmerge．リストのmergeをmergeListとします．

木同士のmergeは以下のように実装されます：

• キー同士を比較し，大きい方を小さい方の子リストに追加．

まあ，普通です．たとえば，要素を延々とpushしていくのは，線形リストの末尾に延々と要素を追加するのと同じ事になります．

続いて，mergeListは以下のようになります：

• リストの先頭から2つずつ要素を取り出し，それらをmergeする（リスト長1/2倍）．
• リストの後ろから順番にmergeして1つの木にする．

１段階目で２つずつ組化することからPairing Heapの名前がきています．１段階目と２段階目でmergeの方向が逆なのは少し重要で，この方向が一番計算時間が短くなります．理論保証するのは大変ですが，実測すると２倍程度の劣化があることがわかります．

C++での実装

上のアルゴリズムをC++に移植する場合に，２つの問題があります：

• 子リストを std::vector などで実装すると，あっさりメモリ溢れする
• mergeList を再帰実装すると，あっさりスタック溢れする

どちらも連続で insert された後のことを考えると，わかると思います．これらの問題が無ければPairing Heapは実装量的にもSkew Heapに匹敵する良データ構造になったのですが……．

どちらの問題も，解決自体は単純です．１つ目の問題は子をきちんとリストでもてばよいだけ．ただし，std::listが頭がオカシイレベルで遅いので，自分で単連結リストを作る必要があります．具体的には，ノードを以下のように定義します．

struct Node {
  int key;
  Node *head;
  Node *next;
};

headは子リストの先頭，nextは自分が含まれているリストにおける自分の次の要素を指します．

２つ目の問題の対応も簡単で，再帰をループに展開するだけです．実際の実装例を以下に示します．

struct PairingHeap {
  struct Node {
    int key;
    Node *head, *next;
    Node(int key) : key(key), head(0), next(0) { }
  } *r;

  Node *merge(Node *i, Node *j) {
    if (!i || !j) return i ? i : j;
    if (i->key > j->key) swap(i, j);
    j->next = i->head; i->head = j;
    return i;
  }
  Node *mergeList(Node *s) {
    Node n(0);
    while (s) {
      Node *a = s, *b = 0;
      s = s->next; a->next = 0;
      if (s) { b = s; s = s->next; b->next = 0; }
      a = merge(a, b); a->next = n.next;
      n.next = a;
    } // s == 0
    while (n.next) {
      Node *j = n.next;
      n.next = n.next->next;
      s = merge(j ,s);
    }
    return s;
  }
  int  top()         { return r->key; }
  void pop()         { r = mergeList(r->head); }
  void push(int key) { r = merge(r, new Node(key)); }
  bool empty()       { return !r; }
  PairingHeap() : r(0) { }
};

実行速度

普段ならここで幾つかの実装と実行速度比較をするところですが，今回はそれは各人のライブラリのマージ可能ヒープと比較してもらうことにします（自分で確認したほうが，わかりやすいと思いますし）．今回は既存の実装例・実行速度比較を紹介します．

C++ の boost に， boost::heap というプロジェクトがあります（http://www.boost.org/doc/libs/1_51_0/doc/html/heap.html）．ここにはいくつかのヒープの実装が置かれており，現在のラインナップは

• binomial heap
• d-ary heap
• fibonacci heap
• pairing heap
• skew heap

となっています．なぜかPairing Heapの実装が２の問題（再帰でスタック溢れ）を対処していない実装になっていますが，それでもそれなりに効率的には実装されています．

これらの実行時間（比較回数）比較が http://boost.2283326.n4.nabble.com/heap-A-performance-test-and-some-questions-tt3575491.html#a3581828 にあるので，見てみると良いかと思います．本当の見所は「効率的に実装されたFibonacci Heapの性能」という，世にも珍しいものだと思っていますが．