厳密なフィボナッチヒープ

厳密なフィボナッチヒープ
タイプ	ヒープ
発明された	2012
発明者	ガース・S・ブローダル、ジョージ・ラゴジャンニス、ロバート・E・タージャン
ビッグO記法の複雑さ
空間複雑性 空間 の上） 時間計算量 関数 償却 最悪の場合 入れる O (1) 最小値を検索 O (1) 削除最小値 O (log n ) 減少キー O (1) マージ O (1)

コンピュータサイエンスにおいて、厳密なフィボナッチヒープは、最悪ケースの時間制限が低い優先キューデータ構造である。これは、最悪ケースにおいてフィボナッチヒープの償却時間制限に一致する。これらの時間制限を達成するために、厳密なフィボナッチヒープは、すべての操作の後に復元変換を実行することで、いくつかの不変量を維持する。これらの変換は、不変条件違反を追跡するための補助データ構造を使用することで定数時間で実行でき、鳩の巣原理によ​​り、これらの違反が修正できることが保証される。厳密なフィボナッチヒープは、2012年にGerth S. Brodal、George Lagogiannis、Robert E. Tarjanによって発明され、2025年に更新された。^{[ 1 ]}

ブロダルキューと共に、厳密なフィボナッチヒープは、優先度キューの漸近的に最適なデータ構造のクラスに属します。 ^{[ 2 ]}厳密なフィボナッチヒープに対するすべての操作は、必然的に対数となるdelete-minを除き、最悪の場合でも定数時間で実行されます。これは最適な方法です。なぜなら、どの優先度キューでも、挿入とdelete-min操作を実行することで要素のリストをソートできるからです。^{[ 3 ]}しかし、厳密なフィボナッチヒープは、動的配列と冗長なカウンタを使用するブロダルキューよりも単純です。^{[ 4 ]}一方、厳密なフィボナッチヒープはポインタベースのみです。 ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

構造

損失のない厳密なフィボナッチヒープ。ノード5と2はアクティブルートです。それらのアクティブサブツリーは二項木です。

厳密なフィボナッチヒープとは、最小ヒープ特性を満たす単一の木です。つまり、ノードのキーは常にその子ノードのキー以下です。結果として、最小のキーを持つノードは常にルートになります。

通常のフィボナッチヒープと同様に、^{[ 5 ]}厳密なフィボナッチヒープは二項式ヒープに似た部分構造を持つ。これらの構造を識別するために、各ノードを2つのタイプのいずれかでラベル付けする。そこで、以下の定義と規則を導入する。

• すべてのノードは、アクティブ(白色) またはパッシブ(赤色)のいずれかです。
• アクティブルートは、パッシブな親を持つアクティブ ノードです。
• パッシブリンク可能ノードとは、そのすべての子孫がパッシブであるパッシブ ノードです(子を持たないパッシブ ノードはリンク可能と見なされます)。
• アクティブ ノードのランクは、そのノードが持つアクティブな子の数です。
• アクティブ ノードの損失は、そのノードが失ったアクティブな子の数です。
• どのノードでも、アクティブな子ノードは、パッシブな子ノードの左側にあります。
• アクティブ ルートの損失は常にゼロです。
• ルートは受動態です。
• ルートの受動的なリンク可能な子要素は、受動的なリンク不可能な子要素の右側にあります。

不変量

不変条件1: 構造

アクティブ ノードの右端の 番目のアクティブな子はを満たします。 ${\displaystyle i}$ ${\displaystyle c_{i}}$ ${\displaystyle c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i-1}$

したがって、アクティブノードの損失は、フィボナッチヒープの「マーク」の一般化と見なすことができます。例えば、損失が0のアクティブノードのみで構成される部分木は二項木です。

さらに、3つの主要な量、すなわち有効根の数、総損失、およびノー​​ドの次数に対数的な上界を課すいくつかの不変量があります。これは、より柔軟で、遅延データ構造であるため、構造違反が のオーダーで増加しても後でクリーンアップできる通常のフィボナッチヒープとは対照的です。 ${\displaystyle O(n)}$

ノードの次数を対数に保つため、ルート以外のすべてのノードはキュー にも参加します。次のセクションとこの記事の残りの部分では、実数 を定義します。ここではヒープ内のノード数、 は2進対数を表します。 ${\displaystyle Q}$ ${\displaystyle R=2\lg n+6}$ ${\displaystyle n}$ ${\displaystyle \lg }$

不変式2: アクティブルート

アクティブルートの合計数は最大 個です。 ${\displaystyle R+1}$

不変条件3: 全損

ヒープ内の合計損失は最大 です。 ${\displaystyle R+1}$

不変式4: 根の次数

ルートの次数は最大 です。 ${\displaystyle R+3}$

不変式5: 非ルート次数

損失がゼロのアクティブノードの場合、次数は最大 です。ここで、は におけるその位置です（最初の要素は 1 です）。ルート以外の他のノードの場合、次数は最大 です。 ${\displaystyle 2\lg(2n-p)+10}$ ${\displaystyle p}$ ${\displaystyle Q}$ ${\displaystyle 2\lg(2n-p)+9}$

系1: 最大度

ルート以外のノードの次数は最大 です。 ${\displaystyle R+6}$

証拠：

これは不変式5から直ちに導かれる。 とすると、 ${\displaystyle p=0}$

${\displaystyle 2\lg(2n-0)+10=2\lg n+12=R+6}$

補題1: 最大ランク

不変条件1が成り立つ場合、最大ランクまたは任意のアクティブノードは最大で であり、ここでは総損失である。^{[ 6 ]} ${\displaystyle r}$ ${\displaystyle \lg n+{\sqrt {2L}}+2}$ ${\displaystyle L}$

証拠：

矛盾を検証しながら進めます。 を、ノード数のヒープにおける最大ランクのアクティブノードとし、 と仮定します。ここでは となる最小の整数です。目標は、をルートとする部分木にノードが含まれることを示すことですが、ヒープには ノードしか存在しないため、これは矛盾です。 ${\displaystyle x}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle r\geq \lg n+k+1}$ ${\displaystyle k}$ ${\displaystyle k(k+1)/2\geq L}$ ${\displaystyle T_{x}}$ ${\displaystyle x}$ ${\displaystyle n+1}$ ${\displaystyle n}$

から受動ノードを根とする部分木をすべて破棄し、能動ノードのみを残す。 の部分木に正の損失を持つノードが含まれる孫ノードをすべて切り捨て、 の子ノードの損失を、失われる孫ノードごとに1回ずつ増加させる。残りのノードの量は変化せず、不変量1が維持される。さらに、損失の合計は最大でも である。 ${\displaystyle T_{x}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \mathrm {rank} +\mathrm {loss} }$ ${\displaystyle L}$

の子ノードは現在、損失のない部分木と正の損失を持つ葉ノードで構成されています。現在、の番目の右端の子ノードに対してが成立します。まず各 の損失を減らし、必要に応じて孫ノードを刈り込むことで、これを正確な等式とします。その後、 が成立します。 の他のすべての子孫ノードも、必要に応じて子ノードを刈り込むことで二項部分木に変換されます。 ${\displaystyle x}$ ${\displaystyle T_{x}}$ ${\displaystyle c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i-1}$ ${\displaystyle i}$ ${\displaystyle c_{i}}$ ${\displaystyle x}$ ${\displaystyle c_{i}}$ ${\displaystyle c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} =i-1}$ ${\displaystyle x}$

ここで、アクティブ ノードを含む次数 の二項木 から始めて、の最小バージョンを再構築します。損失を まで増やしたいのですが、としての のランクとノードの数をできるだけ低く保ちます。次数 の二項木では、から までの各次数に 1 つの子が存在します。したがって、次数 の孫が存在します。次数 の孫をすべて切断すると、孫が切断されることになり、損失を まで下げるのに十分です。次数 のすべての孫は生き残ります。が次数で損失 0の子であるとします。仮定により、、および は完全二項木なので、少なくとも 個のノードがあります。これは が少なくとも 個のノードを持つことを意味するため、矛盾に達し、したがって となります。 に注意すると、 が得られます。 ${\displaystyle T_{x}}$ ${\displaystyle r}$ ${\displaystyle 2^{r}}$ ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle 0}$ ${\displaystyle r-1}$ ${\displaystyle j}$ ${\displaystyle r-j-1}$ ${\displaystyle \leq r-k-1}$ ${\textstyle \sum _{j=1}^{k}j=k(k+1)/2}$ ${\displaystyle L}$ ${\displaystyle \leq r-k-2}$ ${\displaystyle w}$ ${\displaystyle x}$ ${\displaystyle r-k-1}$ ${\displaystyle r-k-1\geq \lg n}$ ${\displaystyle w}$ ${\displaystyle 2^{\lg n}=n}$ ${\displaystyle T_{x}}$ ${\displaystyle n+1}$ ${\displaystyle r<\lg n+k+1}$ ${\displaystyle k<{\sqrt {k(k+1)}}={\sqrt {2L}}}$ ${\displaystyle r<\lg n+{\sqrt {2L}}+2}$

補題2: 最大ランク

不変条件 1 と 3 が両方とも成立する場合、最大ランクは です。 ${\displaystyle R}$

証拠：

不変式3から、 が得られる。これを補題1に代入すると、以下のように計算される。 ${\displaystyle L\leq R+1}$

${\displaystyle {\begin{aligned}r&\leq \lg n+{\sqrt {2L}}+2\\&\leq \lg n+{\sqrt {2(R+1)}}+2\\&=\lg n+{\sqrt {4\lg n+14}}+2\\&\leq \lg n+{\sqrt {(\lg n)^{2}+2\cdot 4\lg n+4^{2}}}+2\\&=\lg n+(\lg n+4)+2\\&=R\end{aligned}}}$

変革

以下の変換は、優先キュー操作の実行後に上記の不変量を復元します。最小化したい主な量は3つあります。アクティブなルートの数、ヒープ内の総損失、そしてルートの次数です。すべての変換は時間内に実行できます。これは、候補ノードを追跡するための補助的なデータ構造を維持することで可能になります（実装のセクションで説明）。^{[ 6 ]} ${\displaystyle O(1)}$

積極的な根の縮小

とを同じランク のアクティブルートとし、 を と仮定します。を の左端の子としてリンクし、 のランクを 1 増やします。の右端の子がパッシブである場合は、ルートにリンクします。 ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle r}$ ${\displaystyle x.\mathrm {key} \leq y.\mathrm {key} }$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle z}$

その結果、アクティブルートではなくなり、アクティブルートの数は1減少します。ただし、ルートノードの次数は1増加する可能性があります。 ${\displaystyle y}$

は の 番目の右端の子となり、ランクは となるため、不変条件 1 は保存されます。 ${\displaystyle y}$ ${\displaystyle (r+1)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle r}$

補題2: 能動的な根削減の可用性

不変条件 2 に違反しているが、不変条件 1 と 3 が保持されている場合、アクティブ ルート削減が可能です。

証拠：

不変式2は破れているため、 個以上のアクティブルートが存在します。系2より、ノードの最大ランクは です。鳩の巣原理より、同じランクのアクティブルートのペアが存在します。 ${\displaystyle R+1}$ ${\displaystyle R}$

損失削減

1ノード損失の削減

を損失が2以上のアクティブな非ルートとします。ルートにリンクしてアクティブルートに変換し、損失を0にリセットします。 の元の親を とします。はアクティブである必要があります。そうでなければ、 は以前アクティブルートであったため、正の損失を持つことができませんでした。 のランクは1減少します。がアクティブルートでない場合は、損失を1増加します。 ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$

全体として、総損失は 1 または 2 減少します。副作用として、ルート次数とアクティブ ルートの数が 1 増加するため、2 ノード損失削減よりも好ましくなくなりますが、それでも必要な操作です。

2ノード損失の削減

と を 、  ランクが等しく損失が 1 であるアクティブノードとし 、を の親とします。一般性を失うことなく、 が であると仮定します。を から切り離し、にリンクします。 のランクを 1 増やし、との損失を1 から 0 にリセットします。 ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle r}$ ${\displaystyle z}$ ${\displaystyle y}$ ${\displaystyle x.\mathrm {key} \leq y.\mathrm {key} }$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle z}$は正の損失を持ち、アクティブルートにはなり得なかったため、アクティブルートでなければなりません。したがって、 のランクは1減少します。がアクティブルートでない場合は、損失を1増加します。 ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle z}$

全体として、総損失は 1 または 2 減少しますが、副作用はありません。

補題3: 損失削減の可用性

不変条件 3 が 1 によって破られるが、不変条件 2 が保持される場合、損失の削減が可能です。

証明：鳩の巣原理を再び適用する。不変式3が1に違反する場合、総損失は となる。補題1は にも当てはまるように書き直すことができる。したがって、系2が成立する。最大ランクは であるため、ランクが等しく損失が1であるアクティブノードのペアが存在するか、 であるアクティブノードが存在する。どちらの場合も、損失削減の機会となる。 ${\displaystyle L=R+2}$ ${\displaystyle L=R+2}$ ${\displaystyle R}$ ${\displaystyle \mathrm {loss} \geq 2}$

根次数削減

根次数削減

、、をルートの右端にある受動的なリンク可能な子3つとする。これらをすべてルートから切り離し、 となるように並べ替える 。 と をアクティブに変更する。にリンクし、にリンクし、をルートの左端の子としてリンクする。その結果、はランク1、損失0のアクティブルートになる。 のランクと損失は0に設定される。 ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x.\mathrm {key} \leq y.\mathrm {key} \leq z.\mathrm {key} }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$

この変換による最終的な変化は、ルート ノードの次数が 2 減少することです。副作用として、アクティブなルートの数が 1 増加します。

補題4: 根次数削減の可用性

不変条件 4 に違反しているが、不変条件 2 が保持されている場合、ルート次数削減は可能です。

証拠：

不変式4が破られる場合、ルートの次数は少なくとも である。ルートの子は、アクティブルート、パッシブ非リンク可能ノード、パッシブリンク可能ノードの3つのカテゴリに分類される。パッシブ非リンク可能ノードはそれぞれ、そのサブツリーに少なくとも1つのアクティブノードが含まれるため、アクティブルートを包含する。アクティブルートの数は最大 であるため、ルートの右端3つの子はパッシブリンク可能でなければならない。 ${\displaystyle R+4}$ ${\displaystyle R+1}$

まとめ

以下の表は、各変換が3つの重要な量に与える影響をまとめたものです。個々の変換は不変条件に違反する可能性がありますが、ここではこれらの量のいずれも増加させない特定の変換の組み合わせのみに着目します。

変換の効果

	活発な根	全損	ルート度
積極的な根の縮小	${\displaystyle -1}$	${\displaystyle 0}$	${\displaystyle 0{\text{ or }}{+}1}$
根次数削減	${\displaystyle +1}$	${\displaystyle 0}$	${\displaystyle -2}$
1ノード損失の削減	${\displaystyle +1}$	${\displaystyle {\text{at least }}{-}1}$	${\displaystyle +1}$
2ノード損失の削減	${\displaystyle 0}$	${\displaystyle -1{\text{ or }}{-}2}$	${\displaystyle 0}$

どの変換を実行するかを決定する際には、簡潔にするために、これらの操作の最悪のケースのみを考慮します。また、2種類の損失削減は同じ操作とみなされます。したがって、「損失削減を実行する」とは、各種類の損失削減を順番に試行することを意味します。

変換の最悪の影響

	活発な根	全損	ルート度
積極的な根の縮小	${\displaystyle -1}$	${\displaystyle 0}$	${\displaystyle +1}$
根次数削減	${\displaystyle +1}$	${\displaystyle 0}$	${\displaystyle -2}$
損失削減	${\displaystyle +1}$	${\displaystyle -1}$	${\displaystyle +1}$

実装

リンクノード

アクティブノードがパッシブノードの左側に配置され、不変条件1が維持されるようにするには、リンク操作においてアクティブノードを左側に、パッシブノードを右側に配置する必要があります。マージ操作によって、小さい方のヒープ内のすべてのノードがパッシブに変更されるため、アクティブノードとパッシブノードが同じリスト内に共存する必要があります。アクティブノードとパッシブノードが別々のリストに存在する場合、リストを連結する必要があり、すべてのノードに対して定数時間で実行することはできません。

ルートについては、受動的でリンク可能な子ノードが受動的でリンク不可能な子ノードの右側にあるという要件も課します。ルートノードへのノードのリンクを定数時間で実行できるようにしたいため、ルートノードの最初の受動的でリンク可能な子ノードへのポインタを保持する必要があります。

候補ノードの検索

不変復元変換は、候補ノードを時間内に見つけられることを前提としています。つまり、同じランクのアクティブルート、同じランクで損失が1のノード、そして損失が2以上のノードを追跡する必要があるということです。 ${\displaystyle O(1)}$

Brodalらによるオリジナルの論文では、候補ノードを追跡する方法として、固定リストとランクリストについて説明しました。 ^{[ 6 ]}

修正リスト

ランクリストと修正リスト

修正リストは 4 つの部分に分かれています。

1. アクティブルートの削減準備が整ったアクティブルート – 同じランクのパートナーを持つアクティブルート。同じランクのノードは隣接したままになります。
2. アクティブ削減の準備ができていないアクティブ ルート - そのランクの唯一のアクティブ ルート。
3. 損失削減の準備ができていない損失 1 のアクティブ ノード – そのランクの損失 1 の唯一のアクティブ ノード。
4. 損失削減の準備ができているアクティブノード – これには、損失が1で同じランクのパートナーを持つアクティブノードと、損失が2以上でパートナーを削減する必要がないアクティブノードが含まれます。同じランクのノードは隣接したままになります。

能動的なルート削減が可能かどうかを確認するには、パート1が空でないかどうかを確認します。空でない場合、最初の2つのノードを削除して変換できます。同様に、損失削減が可能かどうかを確認するには、パート4の末尾を確認します。損失が2以上のノードが含まれている場合、1ノードの損失削減が実行されます。そうでない場合、最後の2つのノードがどちらも損失が1で、同じランクである場合は、2ノードの損失削減が実行されます。

ランキングリスト

ランク リストは、各ランクに関する情報を含む二重にリンクされたリストであり、これにより、同じランクのノードをフィックス リスト内で一緒に組み合わせることができます。

ランクリスト内の ランクを表す各ノードについては、次のものを維持します。 ${\displaystyle r}$

• ランク のフィックスリスト内の最初のアクティブルートへのポインタ。そのようなノードが存在しない場合は、NULL になります。 ${\displaystyle r}$
• ランクと損失が 1 である、修正リスト内の最初のアクティブ ノードへのポインタ。そのようなノードが存在しない場合は、これは NULL になります。 ${\displaystyle r}$
• ランクの増分と減分を容易にするための、ランクとを表すノードへのポインタ。 ${\displaystyle r+1}$ ${\displaystyle r-1}$

修正リストとランク リストには広範な記録が必要であり、新しいアクティブ ノードが発生するたびに、またはノードのランクや損失が変更されるたびに記録を実行する必要があります。

共有フラグ

共有フラグを使用して、すべてのノードを時間内にパッシブに変更する ${\displaystyle O(1)}$

マージ操作は、小さいヒープ内のすべてのアクティブノードをパッシブノードに変更します。これは、間接レベルを導入することで時間内に実行できます。^{[ 6 ]}ブールフラグの代わりに、各アクティブノードはブール値を含むアクティブフラグオブジェクトへのポインタを持ちます。パッシブノードの場合、フラグオブジェクトがパッシブに設定されていれば、どのアクティブフラグオブジェクトを指しているかは関係ありません。これは、多くのパッシブノードを同時にアクティブノードに変更する必要がないためです。 ${\displaystyle O(1)}$

ノードとボックスキー間のポインタの再リンク

キーの保存

キー減少操作では、キーを減少させたいノードへの参照が必要です。しかし、キー減少操作自体がノードのキーとキールートを入れ替えてしまうことがあります。

挿入操作が、パブリック API の一部として、decrease-key を呼び出すことができる不透明な参照を返すと仮定します。これらの参照が内部ヒープ ノードである場合、キーを交換することによってこれらの参照が変化し、他の参照が未定義になります。キーが常に同じ参照に留まるようにするには、キーを「ボックス化」する必要があります。各ヒープ ノードには、キーを含むボックスへのポインターが含まれ、ボックスにはヒープ ノードへのポインターもあります。アイテムを挿入するときに、キーを格納するボックスを作成し、ヒープ ノードとボックスを双方向にリンクして、ボックス オブジェクトを返します。^{[ 6 ]} 2 つのノード間でキーを交換するには、代わりにボックスとノード間のポインターを再リンクします。

オペレーション

マージ

とを厳密なフィボナッチ ヒープとします。どちらかが空の場合は、もう一方を返します。それ以外の場合は、と をそれらの対応するサイズとします。一般性を失うことなく、 と仮定します。各ヒープの fix-list と rank-list のサイズはヒープ サイズに対して対数であるため、これらの補助構造を定数時間でマージすることはできません。代わりに、小さい方のヒープの構造を破棄して、その fix-list と rank-list を破棄し、そのすべてのノードをパッシブ ノードに変換します。^{[ 6 ]}これは、上記で示したように、共有フラグを使用して定数時間で実行できます。 と をリンクして、小さい方のキーを持つルートがもう一方の親になるようにします。と をそれぞれとのキューとします。結果のヒープのキューは に設定され、 は大きい方のキーを持つルートです。 ${\displaystyle h_{1}}$ ${\displaystyle h_{2}}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$ ${\displaystyle n_{1}\leq n_{2}}$ ${\displaystyle h_{1}}$ ${\displaystyle h_{1}}$ ${\displaystyle h_{2}}$ ${\displaystyle Q_{1}}$ ${\displaystyle Q_{2}}$ ${\displaystyle h_{1}}$ ${\displaystyle h_{2}}$ ${\displaystyle Q_{\mathrm {merged} }=Q_{1}+\{r_{\mathrm {larger} }\}+Q_{2}}$ ${\displaystyle r_{\mathrm {larger} }}$

唯一起こり得る構造違反はルート次数です。これは、各変換が可能な場合、1回のアクティブルート簡約と1回のルート次数簡約を実行することで解決されます。

	活発な根	全損	ルート度
マージ後の状態	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle +1}$
${\displaystyle 1\times }$積極的な根の縮小	${\displaystyle -1}$	${\displaystyle 0}$	${\displaystyle +1}$
${\displaystyle 1\times }$根次数削減	${\displaystyle +1}$	${\displaystyle 0}$	${\displaystyle -2}$
合計	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$

正しさの証明

ヒープ構造が破棄されるため、不変条件1、2、3は自動的に成立します。上記の計算結果から、不変条件4の違反はルート次数削減変換によって解決されます。

不変条件5を検証するために、 におけるノードの最終的な位置を考えます。各ノードの次数はまたはで制限されます。 ${\displaystyle Q}$ ${\displaystyle 2\lg(2n-p)+10}$ ${\displaystyle 2\lg(2n-p)+9}$

ヒープが小さい場合、内の位置は変わりません。ただし、 内のすべてのノードはパッシブになり、その制約は状況によって変化する可能性があります。ただし、 であることを考慮すると、結果のサイズは少なくとも の2倍になります。これにより、各制約で少なくとも 1 増加し、前述の懸念は解消されます。 ${\displaystyle h_{1}}$ ${\displaystyle Q_{1}}$ ${\displaystyle h_{1}}$ ${\displaystyle +10}$ ${\displaystyle +9}$ ${\displaystyle n_{1}\leq n_{2}}$ ${\displaystyle n=n_{1}+n_{2}}$ ${\displaystyle n_{1}}$

との間のより大きなキーを持つルートは非ルートとなり、 と の間の位置 に配置されます。不変式4により、その次数は、それがどのヒープから来たかに応じてまたはで制限されます。これはいずれの場合 も より小さいことは容易にわかります。 ${\displaystyle h_{1}}$ ${\displaystyle h_{2}}$ ${\displaystyle Q_{1}}$ ${\displaystyle Q_{2}}$ ${\displaystyle n_{1}}$ ${\displaystyle R_{1}+3=2\lg n_{1}+9}$ ${\displaystyle R_{2}+3=2\lg n_{2}+9}$ ${\displaystyle 2\lg {(2n_{1}+2n_{2}-n_{1})}+9}$

ヒープが大きいほど、位置は だけ増加します。しかし、結果として得られるサイズは なので、値は実際には増加し、制約が弱まります。 ${\displaystyle n_{1}}$ ${\displaystyle n=n_{1}+n_{2}}$ ${\displaystyle 2n-p}$

入れる

挿入はマージ操作の特殊なケースと考えることができます。単一のキーを挿入するには、1つのパッシブノードと空のキューを含む新しいヒープを作成し、それをメインヒープとマージします。

最小値を検索

最小ヒープ プロパティにより、最小キーを持つノードが存在する場合は常にルートになります。

削除最小値

最小値削除操作

ヒープ内にルートノードが1つしかない場合は、ルートノードを削除するだけで完了です。そうでない場合は、ルートノードの子ノードを検索してキーが最小のノードを見つけ、新しいルートノードを に設定します。がアクティブの場合は、 をパッシブノードに変更し、 のすべてのアクティブな子ノードが暗黙的にアクティブルートノードになります。古いルートノードの子ノードを にリンクします。がルートになったので、 のリンク可能なパッシブノードをすべて右に移動し、から を削除します。 ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle Q}$

ルートの次数はほぼ2倍になります。これは、古いルートのすべての子を にリンクしたためです。以下の復元変換を実行します。 ${\displaystyle x}$

1. 2 回繰り返します。のヘッドを後ろに移動して回転させ、 の右端の 2 つのパッシブな子要素をルートにリンクします。 ${\displaystyle Q}$ ${\displaystyle y}$ ${\displaystyle Q}$ ${\displaystyle y}$
2. 損失削減が可能な場合はそれを実行します。
3. どちらも不可能になるまで、アクティブなルート削減とルート次数削減を実行します。

ステップ 3 がどのように制限されるかを確認するには、ステップ 3 後の状態を考えます。

	活発な根	全損	ルート度
削除最小後の状態	${\displaystyle +R}$	${\displaystyle 0}$	${\displaystyle +R+6}$
${\displaystyle 2\times }$キューのローテーション	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle +4}$
${\displaystyle 1\times }$損失削減	${\displaystyle +1}$	${\displaystyle -1}$	${\displaystyle +1}$
合計	${\displaystyle +R+1}$	${\displaystyle -1}$	${\displaystyle +R+11}$

3 つの有効なルート削減と 2 つのルート削減により、ルート次数と有効なルートが 1 減少することに注意してください。

	活発な根	全損	ルート度
${\displaystyle 3\times }$積極的な根の縮小	${\displaystyle -3}$	${\displaystyle 0}$	${\displaystyle +3}$
${\displaystyle 2\times }$根次数削減	${\displaystyle +2}$	${\displaystyle 0}$	${\displaystyle -4}$
合計	${\displaystyle -1}$	${\displaystyle 0}$	${\displaystyle -1}$

なので、ステップ 3 は 回以上実行されることはありません。 ${\displaystyle R=2\lg n+6}$ ${\displaystyle O(\log n)}$

正しさの証明

アクティブルートは作成されないため、不変条件 1 は自明に成立します。

ヒープのサイズが1減少し、最大1の減少が発生します。したがって、不変条件3は最大1によって破られます。補題3により、ステップ2で既に実行されている損失削減が可能です。 ${\displaystyle n}$ ${\displaystyle R=2\lg n+6}$

不変条件1と3は成立する。ステップ3の後も不変条件2と4が破られる場合、補題2と4により、active root liningとroot degree liningを適用できる。しかし、active root liningとroot degree liningは既に網羅的に適用されている。したがって、不変条件2と4も成立する。

不変条件5が満たされていることを示すために、まずヒープサイズが1減少したことに注目します。ステップ1で最初の2つのノードがポップされるため、ステップ2の他の要素の位置は2減少します。したがって、これらのノードの次数制約と次数は一定のままです。以前にポップされた2つのノードは、ステップ3でそれぞれ位置1と2でしたが、現在はそれぞれ位置と位置にあります。その結果、次数制約は2強化されますが、これらのノードそれぞれについて受動的な子ノードを2つ削除することで、制約を再び満たすことができます。 ${\displaystyle n}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle 2\lg(2n-p)+10}$ ${\displaystyle 2\lg(2n-p)+9}$ ${\displaystyle Q}$ ${\displaystyle n-2}$ ${\displaystyle n-1}$

減少キー

減少キー操作

キーが減少したノードをとします。がルートであれば、処理は完了です。 がルートでない場合は、 をルートとする部分木を切り離し、ルートにリンクします。 のキーがルートのキーよりも小さい場合は、それらのキーを交換します。 ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

最大3つの構造違反が発生した可能性があります。が既にルートの子でない限り、ルートの次数は1増加します。が元の親から切り離された場合、以下のケースが発生します。 ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$

• が受動的である場合、追加の違反はありません。 ${\displaystyle x}$
• が以前はパッシブのアクティブ ルートであった場合、の子からルートの子に移動しても、追加のアクティブ ルートは作成されず、ノードの損失も増加しません。 ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$
• と の両方がアクティブな場合、 の損失は1 増加し、追加のアクティブ ルートが作成されます (ルートにリンクすることにより)。 ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$

最悪の場合、3 つの量 (ルート次数、総損失、アクティブ ルート) すべてが 1 増加します。

1 回の損失削減を実行した後でも、最悪の結果では、ルート次数とアクティブ ルートの数はどちらも 2 増加しています。これらの違反を修正するには、3 回のアクティブ ルート削減と 2 回のルート削減によって、これらの量が両方とも 1 減少するという事実を利用します。したがって、これらの変換をそれぞれ 6 回と 4 回適用すれば、すべての違反を排除するのに十分です。

	活発な根	全損	ルート度
減少キー後の状態	${\displaystyle +1}$	${\displaystyle +1}$	${\displaystyle +1}$
${\displaystyle 1\times }$損失削減	${\displaystyle +1}$	${\displaystyle -1}$	${\displaystyle +1}$
${\displaystyle 6\times }$積極的な根の縮小	${\displaystyle -6}$	${\displaystyle 0}$	${\displaystyle +6}$
${\displaystyle 4\times }$根次数削減	${\displaystyle +4}$	${\displaystyle 0}$	${\displaystyle -8}$
合計	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$

正しさの証明

以前 の左兄弟であったノードは、によって生じた隙間を埋めるために移動し、インデックスを減少させます。制約が弱まるため、不変式1は影響を受けません。不変式5は、 が変化しないため、自明に成立します。 ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle Q}$

補題2、3、4は、能動的な根簡約、損失簡約、および根次数簡約が利用可能であることを保証する。したがって、不変条件2、3、4は成立する。

パフォーマンス

厳密なフィボナッチヒープは理論的には最適ですが、実用的ではありません。実装が非常に複雑で、ノードごとに10個以上のポインタの管理が必要になります。^{[ 6 ] [ 7 ]}ほとんどの操作は時間内に実行されますが、定数係数が非常に高くなる場合があり、バイナリヒープやペアリングヒープなどのより一般的なヒープと比較して最大20倍遅くなります。^{[ 8 ]}比較的単純であるにもかかわらず、実験では、厳密なフィボナッチヒープは実際にはブロダルキューよりも遅いことが示されています。^{[ 9 ]} ${\displaystyle O(1)}$

実行時間の概要

様々なヒープデータ構造の時間計算量^{[ 10 ]}を以下に示します。略語am.は、与えられた計算量が償却されることを示し、そうでない場合は最悪ケースの計算量です。「O ( f )」および「Θ ( f )」の意味については、 Big O記法を参照してください。演算名は最小ヒープを前提としています。

手術	最小値を見つける	削除最小値	減少キー	入れる	融合する	ヒープを作る[ a ]
バイナリ[ 10 ]	Θ (1)	Θ (log  n )	Θ (log  n )	Θ (log  n )	Θ ( n )	Θ ( n )
スキュー[ 11 ]	Θ (1)	O (log  n )午前。	O (log  n )午前。	O (log  n )午前。	O (log  n )午前。	Θ ( n )午前。
左翼[ 12 ]	Θ (1)	Θ (log  n )	Θ (log  n )	Θ (log  n )	Θ (log  n )	Θ ( n )
二項分布[ 10 ] [ 14 ]	Θ (1)	Θ (log  n )	Θ (log  n )	Θ（１）午前。	Θ (log  n ) [ b ]	Θ ( n )
歪んだ二項分布[ 15 ]	Θ (1)	Θ (log  n )	Θ (log  n )	Θ (1)	Θ (log  n ) [ b ]	Θ ( n )
2～3山[ 17 ]	Θ (1)	O (log  n )午前。	Θ (1)	Θ（１）午前。	O (log  n ) [ b ]	Θ ( n )
ボトムアップの歪み[ 11 ]	Θ (1)	O (log  n )午前。	O (log  n )午前。	Θ（１）午前。	Θ（１）午前。	Θ ( n )午前。
ペアリング[ 18 ]	Θ (1)	O (log  n )午前。	o (log  n ) am. [ c ]	Θ (1)	Θ (1)	Θ ( n )
ランクペアリング[ 21 ]	Θ (1)	O (log  n )午前。	Θ（１）午前。	Θ (1)	Θ (1)	Θ ( n )
フィボナッチ[ 10 ] [ 22 ]	Θ (1)	O (log  n )午前。	Θ（１）午前。	Θ (1)	Θ (1)	Θ ( n )
厳密なフィボナッチ[ 23 ] [ d ]	Θ (1)	Θ (log  n )	Θ (1)	Θ (1)	Θ (1)	Θ ( n )
ブロダル[ 24 ] [ d ]	Θ (1)	Θ (log  n )	Θ (1)	Θ (1)	Θ (1)	Θ ( n ) [ 25 ]

1. make-heap は、 n個の未ソート要素のシーケンスからヒープを構築する操作である。meld がO (log  n ) 時間で実行される場合、 make-heapはΘ ( n ) 時間で実行できる^{（ただし、両方の計算量は償却可能である）。 [ 11 ] [ 12 ]}別のアルゴリズムでは、バイナリヒープに対してΘ ( n )時間。 ^{[ 13 ]}
2. 永続ヒープ（decrece-keyをサポートしていない）の場合、一般的な変換により、meldのコストが挿入のコストまで削減されます。delete -minの新しいコストは、 delete-minとmeldの古いコストの合計になります。^{[ 16 ]}ここで、meldはΘ (1)時間（挿入のコストが償却される場合）で実行されますが、 delete-minは依然としてO（log  n）で実行されます。これを歪んだ二項ヒープに適用すると、最悪のケースの複雑さが最適な永続ヒープであるBrodal-Okasakiキューが生成されます。^{[ 15 ]}
3. ^{[ 19 ]}の下限値^{[ 20 ]}の上限値 ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
4. Brodalキューと厳密なフィボナッチヒープは、ヒープの最悪ケース計算量を最適化する。これらは当初、命令型データ構造として記述された。Brodal-Okasakiキューは、減少キーがサポートされていないことを除いて、同様の最適化を実現する永続的データ構造である。

参考文献

1. ブローダル、ガース・ストルティング;ラゴジャンニス、ジョージ。タージャン、ロバート E. (2025) 「厳密なフィボナッチ ヒープ」。アルゴリズムに関する ACM トランザクション。21 (2): 1–18 .土井: 10.1145/3707692。
2. Brodal, Gerth Stølting; Okasaki, Chris (1996年11月). 「最適な純粋機能的優先キュー」 . Journal of Functional Programming . 6 (6): 839– 857. doi : 10.1017/S095679680000201X . ISSN 0956-7968 . 
3. Knuth, Donald E. (1998-04-24). 『コンピュータプログラミングの芸術：ソートと検索』第3巻. Addison-Wesley Professional. ISBN 978-0-321-63578-5。
4. Brodal, Gerth Stølting (1996-01-28). 「最悪ケースにおける効率的な優先キュー」 .第7回ACM-SIAM離散アルゴリズムシンポジウム議事録. SODA '96. 米国応用数学協会: 52–58 . ISBN 978-0-89871-366-4。
5. Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). 「フィボナッチヒープと改良ネットワーク最適化アルゴリズムにおけるその利用」 . Journal of the ACM . 34 (3): 596– 615. doi : 10.1145/28869.28874 . ISSN 0004-5411 . 
6. Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012-05-19). 「厳密なフィボナッチヒープ」 .第44回ACMコンピューティング理論シンポジウム議事録. STOC '12. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  1177– 1184. doi : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5。
7. Majerech, Vladan (2019-11-25)、最悪ケース拡張による高速フィボナッチヒープ、arXiv : 1911.11637
8. ラーキン, ダニエル; セン, シッダールタ; タージャン, ロバート (2014). 「優先キューの基本に立ち返った実証的研究」.第16回アルゴリズム工学と実験ワークショップ議事録: 61–72 . arXiv : 1403.0252 . Bibcode : 2014arXiv1403.0252L . doi : 10.1137/1.9781611973198.7 . ISBN 978-1-61197-319-8. S2CID  15216766 .
9. Mrena, Michal; Sedlacek, Peter; Kvassay, Miroslav (2019年6月). 「最短経路探索における優先度キューの高度な実装の実用的適用性」. 2019 International Conference on Information and Digital Technologies (IDT) . Zilina, Slovakia: IEEE. pp.  335– 344. doi : 10.1109/DT.2019.8813457 . ISBN 9781728114019. S2CID  201812705 .
10. コーメン、トーマス H. ;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。
11. Sleator, Daniel Dominic ; Tarjan, Robert Endre (1986年2月). 「自己調整ヒープ」 . SIAM Journal on Computing . 15 (1): 52– 69. CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
12. Tarjan, Robert (1983). 「3.3. 左派ヒープ」.データ構造とネットワークアルゴリズム. pp.  38– 42. doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5。
13. Hayward, Ryan; McDiarmid, Colin (1991). 「繰り返し挿入によるヒープ構築の平均ケース分析」(PDF) . J. Algorithms . 12 : 126–153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . 2016年2月5日時点のオリジナル(PDF)からアーカイブ。 2016年1月28日閲覧。 
14. 「二項式ヒープ | Brilliant Math & Science Wiki」brilliant.org . 2019年9月30日閲覧。
15. Brodal, Gerth Stølting; Okasaki, Chris (1996年11月)、「最適な純粋機能的優先度キュー」、Journal of Functional Programming、6 (6): 839– 857、doi : 10.1017/s095679680000201x
16. Okasaki, Chris (1998). 「10.2. 構造的抽象化」.純粋関数型データ構造（第1版）. pp.  158– 162. ISBN 9780521631242。
17. 高岡忠雄(1999) 「2-3ヒープ理論」 (PDF)、p.12
18. Iacono, John (2000)、「ペアリングヒープの改良された上限値」、Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF)、Lecture Notes in Computer Science、vol. 1851、Springer-Verlag、pp.  63– 77、arXiv : 1110.4428、CiteSeerX 10.1.1.748.7812、doi : 10.1007/3-540-44985-X_5、ISBN  3-540-67690-2
19. Fredman, Michael Lawrence (1999年7月). 「ペアリングヒープと関連データ構造の効率について」(PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .
20. ペティ, セス (2005).ペアリングヒープの最終分析に向けて(PDF) . FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp.  174– 183. CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN  0-7695-2468-0。
21. ハウプラー、ベルンハルト;セン、シッダールタ。タージャン、ロバート E. (2011 年 11 月) 「ランクペアリングヒープ」(PDF)。サイアム J. コンピューティング。40 (6): 1463 ～ 1485 年。土井: 10.1137/100785351。
22. Fredman, Michael Lawrence ; Tarjan, Robert E. (1987年7月). 「フィボナッチヒープと改良ネットワーク最適化アルゴリズムにおけるその利用」(PDF) . Journal of the Association for Computing Machinery . 34 (3): 596– 615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
23. Brodal, Gerth Stølting ; Lagogiannis, George ; Tarjan, Robert E. (2012).厳密なフィボナッチヒープ(PDF) . Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp.  1177– 1184. CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN  978-1-4503-1245-5。
24. Brodal, Gerth S. (1996)、「最悪ケースの効率的な優先キュー」（PDF）、第7回ACM-SIAM離散アルゴリズムシンポジウム論文集、pp.  52– 58
25. Goodrich, Michael T. ; Tamassia, Roberto (2004). 「7.3.6. ボトムアップヒープ構築」. 『Javaにおけるデータ構造とアルゴリズム』（第3版）. pp.  338– 341. ISBN 0-471-46983-1。

外部リンク

• 厳密なフィボナッチヒープのJavaScriptシミュレーション

「 https://en.wikipedia.org/w/index.php?title=Strict_Fibonacci_heap&oldid=1317869600」より取得