フィボナッチヒープとは?データ構造の基本と特徴をわかりやすく解説
フィボナッチヒープとは
フィボナッチヒープ(Fibonacci Heap)は、二項ヒープ(Binomial Heap)と同様に、複数の木から構成されるデータ構造です。二項ヒープを緩くベースとしていますが、両者には重要な違いがあります。二項ヒープ内部の木が「順序付けられた木(ordered tree)」であるのに対し、フィボナッチヒープ内部の木は根(root)を持ちますが、順序付けられていない点が特徴です。
ノードの構造
フィボナッチヒープ内の各ノード x は、以下のようなポインタを持っています。
- p[x]:親ノードを指すポインタ
- child[x]:自身の子のうち任意の1つを指すポインタ
ノード x の子同士は、「子リスト(child list)」と呼ばれる循環双方向連結リスト(circular doubly linked list)によって相互に接続されています。
子リスト内の各子ノード y は、左隣・右隣の兄弟ノードを指すポインタ left[y] および right[y] を持っています。もし y が唯一の子であれば、left[y] = right[y] = y となります。また、子リスト内における兄弟ノードの並び順は任意であり、特定の順序に制限されません。
フィボナッチヒープの例
下図はフィボナッチヒープ H の一例です。
このヒープ H は、5本のフィボナッチ木(根を持つ木)と16個のノードで構成されています。矢印付きの線はルートリスト(root list)を表しており、リスト内の最小ノードは min[H] によって示されます。この例では、min[H] が値「4」を保持するノードを指しています。
主な操作と計算量
フィボナッチヒープは、償却解析(amortized analysis)に基づく優れた計算量を持つことで知られています。
- 挿入(insert):O(1)
- 最小値の参照(find-min):O(1)
- キーの減少(decrease-key):O(1)(償却)
- 最小値の削除(extract-min):O(log n)(償却)
特に decrease-key 操作を定数時間で行える点が大きな強みであり、これがグラフアルゴリズムの高速化に大きく寄与しています。
応用分野
フィボナッチヒープは、最小全域木(Minimum Spanning Tree)の計算や単一始点最短経路問題(Single Source Shortest Path)などを解く、漸近的に高速なアルゴリズムにおいて本質的な役割を果たします。代表例としては、ダイクストラ法(Dijkstra's algorithm)やプリム法(Prim's algorithm)との組み合わせが挙げられます。
-
インターバルヒープ（区間ヒープ）とは？データ構造の基本をわかりやすく解説
インターバルヒープとはインターバルヒープ（Interval Heap）は、両端優先度キュー（Double-Ended Priority Queue）を効率的に実装するために用いられるデータ構造です。完全二分木の一種であり、最後のノードを除くすべてのノードが2つの要素を持つという特徴があります。ノードと区間の関係ノードPに格納された2つの要素の優先度を「a」と「b」とし、a ≤ b が成り立つものとします。このとき、ノードPは閉区間 [a, b] を表すと定義されます。ここで、a を区間の左端点、b を右端点と呼びます。ある区間 [c, d] が区間 [a, b] に包含されるのは、次の条件が成
-
ハーフエッジデータ構造（HalfedgeDS）とは？基本概念とCGAL実装例をわかりやすく解説
はじめにテンプレートパラメータとして用いられるハーフエッジデータ構造（Halfedge Data Structure、略称 HalfedgeDS）は、頂点・辺・面の接続情報（インシデンス情報）を管理できる、辺を中心としたデータ構造として定義されています。平面地図（planar map）や多面体など、任意の次元空間に埋め込まれた向き付け可能な2次元曲面の表現に適した構造です。このデータ構造では、各辺が逆向きの向きを持つ2つのハーフエッジ（半辺）に分割されます。各ハーフエッジは、隣接する1つの面と1つの頂点への参照を保持し、逆に各面および各頂点にも、それぞれ1つの接続ハーフエッジが格納されます。さ