フィボナッチヒープの構造
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/21 22:30 UTC 版)
「フィボナッチヒープ」の記事における「フィボナッチヒープの構造」の解説
フィボナッチヒープはminimum-heap propertyを満足する木の集まりである。つまり、ある子のキーは常に親のキーよりも等しいか大きい。つまり最小のキーは常に何れかの木のルートにある。二項ヒープと比較してフィボナッチヒープの構造はより柔軟である。木は規定された形を特に持っておらず、極端な場合はヒープ中の n 個の要素が全て別々の（n 個の）木に属しているかもしれないし、深さ n の一つの木に属しているかもしれない。この柔軟さによって、ある種の操作を後回しにするなど「怠惰な」処理方法が許される。例えば、二つのヒープを結合するには単に二つのヒープの木のリストを連結するだけで良いし、「キーの減算」操作の過程ではあるノードが親から切り離されて新しい木を作る場合がある。 しかしながら、処理時間を抑えるためには、何らかの時点でヒープにある種の秩序を導入しなければならない。特に、ノードの次数(＝ノードが直接持つ子の数)はかなり小さく抑えられる：個々のノードの次数はたかだか O(log n) であり、かつ、次数 k のノードが持つサブツリーの大きさは少なくとも Fk + 2 である（ここで Fk は k 番目のフィボナッチ数）。これを守るために、ルートでないノードからはたかだか一つの子しか切り取れないという規約を作る。二つ目の子を切り取る場合は、そのノード自身も親から切り取って新しい木のルートにする。木全体の数は「最小値の削除」操作によって木同士を繋ぐことで減少する。 柔軟な構造を持つために、一部の操作には長い時間がかかる一方、他の操作は非常に速く終わるということが起きる。走行時間の償却解析においては、「非常に速い操作」の所要時間は実際の所要時間よりも若干長いものとして扱う。この余分な時間は、後に「遅い操作」が実際に要した時間から差し引かれる。後で使うために取っておかれている時間の量は、任意の時点でポテンシャル関数によって計測される。フィボナッチヒープのポテンシャル関数は次式によって与えられる。 P o t e n t i a l = t + 2 m {\displaystyle Potential=t+2m} ここで t はフィボナッチヒープの中にある木の数、m はマークされたノードの数である。あるノードは、自身が他のノードの子となって以降、自身の子が少なくとも一つ切り取られたならばマークされる（但しルートはマークせず、マークされたノードがルートになった場合はマークを消す）。 従って、ヒープ内のそれぞれの木のルートは 1 単位時間を保持している。この単位時間は後でこの木を他の木と償却時間 0 でリンクするのに使うことができる。また、個々のマークされたノードは 2 単位時間を保持している。このうち 1 単位時間はそのノードを親から切り離すのに使うことができる。もしこれが起きると、そのノードはルートとなり、残る 2 つめの単位時間を他のルートと同様に保持し続けることになる。
※この「フィボナッチヒープの構造」の解説は、「フィボナッチヒープ」の解説の一部です。
「フィボナッチヒープの構造」を含む「フィボナッチヒープ」の記事については、「フィボナッチヒープ」の概要を参照ください。
- フィボナッチヒープの構造のページへのリンク
