2009年04月01日

Driscoll, J. R., Gabow, H. N., Shrairman, R., and Tarjan, R. E. Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31, 11 (Nov. 1988), 1343-1354.

実用的に使える，殆どの演算がフィボナッチヒープと同じ計算量になるヒープ．二項ヒープがベース．

ただの二項ヒープだとすべての演算がO(log n)だけど（ノード数nで），ヒープ条件満たさないノードが log n 個くらいあってもいいよねとする．結果として，insert と decrease_key が O(1) になる．最小を取ってくる delete_min と最小を見る find_min とヒープをマージする union は O(log n) を保つ．フィボナッチヒープの decrease_key はならしでO(1)だけど，Relaxed heap のは最悪計算量でO(1)である点が賢い．

基本，ヒープ条件を壊したノードを覚えておいて，その数が log n を超えたときにはO(1)の操作でヒープ条件を壊したノードの数を1以上減らす．ヒープ条件を壊したノードのペアを持ってきて，適当にノードの入れ替えをすると条件を満たさないノードの数が減る．この操作をO(1)でやるために条件を壊したノードの連続やペアを保持するリストを余計に持っていると．

最小の取り出しやマージの計算量は，通常の二項ヒープと同様，log n 回二項木を結合すれば操作が完了することから保証される．最小の読み出しの計算量は，最小値が各二項木のルート（最大 log n個）かヒープ条件を壊したノード（最大 log n個）であることから O(log n) になると．

そしてこれがどのように最短路の並列計算に使えるのかはまだ読んでいない．