ヒープ（データ構造）

コンピュータサイエンスにおいて、ヒープとは、ヒープ特性を満たすツリーベースのデータ構造である。最大ヒープでは、任意のノードCについて、PがCの親ノードであれば、 Pのキー（値）はCのキー以上である。最小ヒープでは、PのキーはCのキー以下である。^[1]ヒープの「最上部」にあるノード（親がない）はルートノードと呼ばれる。

ヒープは、優先度キューと呼ばれる抽象データ型の最も効率的な実装の 1 つであり、実際に、優先度キューは、実装方法に関係なく、「ヒープ」と呼ばれることがよくあります。ヒープでは、最も高い (または最も低い) 優先度の要素が常にルートに格納されます。ただし、ヒープはソートされた構造ではなく、部分的に順序付けられていると考えることができます。ヒープは、最も高い (または最も低い) 優先度のオブジェクトを繰り返し削除する必要がある場合、またはルートノードの削除と挿入を交互に行う必要がある場合に便利なデータ構造です。

ヒープの一般的な実装はバイナリヒープであり、その木は完全な^[2]バイナリ木です (図を参照)。ヒープデータ構造、特にバイナリヒープは、 1964 年にJWJ Williamsによってヒープソートソートアルゴリズムのデータ構造として導入されました。 ^{[3]ヒープは、}ダイクストラのアルゴリズムなどのいくつかの効率的なグラフアルゴリズムでも重要です。ヒープが完全なバイナリ木である場合、その高さは最小になります。つまり、N個のノードと各ノードのブランチを持つヒープの高さは常に log _a Nになります。

図に示されているように、兄弟やいとこ同士の順序は暗黙的に決まっておらず、また、順序どおりにトラバースする場合の順序も暗黙的に決まっていないことに注意してください (たとえば、バイナリ検索ツリーの場合のように)。上記のヒープ関係は、ノードとその親、つまり祖父母の間にのみ適用されます。各ノードが持つことができる子の最大数は、ヒープの種類によって異なります。

ヒープは通常、要素が格納されている同じ配列内にインプレースで構築され、その構造は操作のアクセスパターンに暗黙的に反映されます。この点でヒープは、キーを格納するために使用されるメモリ以外に追加のメモリを必要としない点で、 Radix ツリーなどの同様の、または場合によってはより優れた理論的境界を持つ他のデータ構造とは異なります。

オペレーション

ヒープに関連する一般的な操作は次のとおりです。

基本

find-max (またはfind-min ): それぞれ最大ヒープ内の最大項目、または最小ヒープ内の最小項目を検索します (別名peek )
挿入: ヒープに新しいキーを追加する(別名プッシュ^[4] )
extract-max（またはextract-min）：最大ヒープから最大値のノード（または最小ヒープから最小値）をヒープから削除した後、それを返す（別名、pop ^[5]）。
delete-max (またはdelete-min ): それぞれ最大ヒープ (または最小ヒープ) のルートノードを削除します。
replace : ルートをポップし、新しいキーをプッシュします。これは、ポップしてからプッシュするよりも効率的です。バランスを取るのが2回ではなく1回だけで済み、固定サイズのヒープに適しているからです。^[6]

創造

create-heap : 空のヒープを作成する
heapify : 指定された要素の配列からヒープを作成する
マージ(和集合): 2 つのヒープを結合して、元のヒープを保持しながら、両方のすべての要素を含む有効な新しいヒープを形成します。
結合: 2 つのヒープを結合して、両方のすべての要素を含む有効な新しいヒープを形成し、元のヒープを破棄します。

検査

size : ヒープ内のアイテムの数を返します。
is-empty : ヒープが空の場合は true を返し、それ以外の場合は false を返します。

内部

増加キーまたは減少キー: それぞれ最大ヒープまたは最小ヒープ内のキーを更新する
delete : 任意のノードを削除します (その後、最後のノードを移動し、ヒープを維持するためにふるいにかけます)
sift-up : 必要なだけツリー内のノードを上に移動します。挿入後にヒープ状態を復元するために使用されます。ノードは、ふるいのように、正しいレベルに達するまでツリーを上方に移動するため、「sift」と呼ばれます。
sift-down : sift-up と同様に、ツリー内のノードを下に移動します。削除または置き換え後にヒープ状態を復元するために使用されます。

実装

ヒープは通常、次のように配列を使用して実装されます。

配列の各要素はヒープのノードを表し、
親子関係は、配列内の要素のインデックスによって暗黙的に定義されます。

ノードキーが 1 から 100 までの整数である完全なバイナリ最大ヒープと、それが配列に格納される方法の例。

バイナリヒープの場合、配列の最初のインデックスにはルート要素が含まれます。配列の次の 2 つのインデックスには、ルートの子が含まれます。次の 4 つのインデックスには、ルートの 2 つの子ノードの 4 つの子が含まれます。以下同様に続きます。したがって、インデックス $iのノードの場合、その子はインデックス$ ⁠ ⁠ $2i+1$ と⁠ ⁠ $2i+2$ にあり、親はインデックス $⌊(i -1)/2⌋$ にあります。この単純なインデックス方式により、ツリーを「上」または「下」に移動するのが効率的になります。

ヒープのバランス調整は、シフトアップまたはシフトダウン操作 (順序が正しくない要素のスワップ) によって行われます。追加のメモリ (たとえばノード用) を必要とせずに配列からヒープを構築できるため、ヒープソートを使用して配列をその場でソートできます。

ヒープに対して要素が挿入または削除された後、ヒーププロパティが違反される可能性があり、配列内の要素を交換してヒープのバランスを再調整する必要があります。

ヒープの種類によって操作の実装方法は異なりますが、最も一般的な方法は次のとおりです。

挿入:ヒープの末尾の最初の使用可能な空き領域に新しい要素を追加します。これがヒーププロパティに違反する場合は、ヒーププロパティが再確立されるまで新しい要素をふるいにかけます ( swim操作)。
抽出:ルートを削除し、ヒープの最後の要素をルートに挿入します。これによりヒーププロパティが違反する場合は、新しいルートをシフトダウン (シンク操作) してヒーププロパティを再確立します。
置換:ルートを削除し、新しい要素をルートに配置してシフトダウンします。抽出後に挿入する場合と比較すると、これによりシフトアップの手順が回避されます。

与えられた配列の要素からバイナリ（またはd進）ヒープを構築することは、古典的なフロイドアルゴリズムを使用して線形時間で実行できます。最悪の場合の比較回数は 2 N − 2 s ₂ ( N ) − e ₂ ( N ) （バイナリヒープの場合）に等しくなります。ここで、s ₂ ( N ) はNのバイナリ表現のすべての桁の合計であり、e ₂ ( N ) はNの素因数分解における 2 の指数です。^[7]これは、元々空のヒープへの連続した挿入のシーケンス（対数線形）よりも高速です。^[a]

バリエーション

バリアントの理論的境界の比較

ここに、さまざまなヒープデータ構造の時間計算量^[8]を示します。略語am.は、指定された計算量が償却されることを示し、そうでない場合は最悪の計算量です。「 O ( f )」および「Θ ( f )」の意味については、Big O 表記法を参照してください。操作の名前は最大ヒープを想定しています。

^ 各挿入にはヒープの既存サイズでO(log( k )) かかります。なので、これらの挿入の定数倍（半分）は最大値の定数倍以内であり、漸近的にと仮定できます。正式には、時間はです。これはスターリングの近似からも容易にわかります。 $\sum _{k=1}^{n}O(\log k)$ $\log n/2=(\log n)-1$ $k=n$ $nO(\log n)-O(n)=O(n\log n)$
^ ヒープ作成はn個の未ソート要素のシーケンスからヒープを構築する操作です。これはΘ ( n )時間で実行できますが、 meldはO (logn )時間で実行できます(両方の計算量が償却できる場合)。^[9]^[10]別のアルゴリズムでは、バイナリヒープに対してΘ ( n )を達成しています。^[11]
^ abc 永続ヒープ（ increase-keyをサポートしない）の場合、一般的な変換により、 meldのコストがinsertのコストまで削減されますが、 delete-maxの新しいコストは、 delete-maxとmeldの古いコストの合計になります。^[14]ここで、meld はΘ (1) 時間（挿入のコストが償却される場合は償却）で実行されますが、 delete-max は依然としてO (log n )で実行されます。これを歪んだ二項ヒープに適用すると、最悪の場合の複雑さが最適な永続ヒープである Brodal-Okasaki キューが生成されます。^[13]
^ ^[17]の下限値、^[18]の上限値 $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$
^ ab Brodal キューと厳密なフィボナッチヒープは、ヒープの最悪ケースの複雑さを最適化します。これらは、最初は命令型データ構造として説明されました。Brodal-Okasaki キューは、増加キーがサポートされていないことを除いて、同じ最適化を実現する永続的なデータ構造です。

アプリケーション

ヒープデータ構造には多くの用途があります。

ヒープソート: インプレースであり、二次最悪のシナリオがない最良のソート方法の 1 つです。
選択アルゴリズム：ヒープは最小要素または最大要素に定数時間でアクセスすることを可能にし、他の選択（中央値やk番目の要素など）はヒープ内のデータに対して線形以下の時間で実行できます。^[24]
グラフアルゴリズム: ヒープを内部トラバーサルデータ構造として使用することで、実行時間が多項式オーダーで短縮されます。このような問題の例としては、Prim の最小全域木アルゴリズムやDijkstra の最短経路アルゴリズムなどがあります。
優先キュー: 優先キューは、「リスト」や「マップ」のような抽象的な概念です。リストがリンクリストや配列で実装できるのと同様に、優先キューはヒープやその他のさまざまな方法で実装できます。
K ウェイマージ: ヒープデータ構造は、既にソートされた多数の入力ストリームを 1 つのソートされた出力ストリームにマージするのに役立ちます。マージが必要な例としては、外部ソートや、ログ構造のマージツリーなどの分散データからのストリーミング結果などがあります。内部ループは、最小要素を取得し、対応する入力ストリームの次の要素に置き換えてから、ヒープのシフトダウン操作を実行します (または、置換関数を使用します)。(優先キューの extract-max 関数と insert 関数を使用すると、効率が大幅に低下します。)

プログラミング言語の実装

C ++ 標準ライブラリは、任意のランダムアクセスイテレータで動作するヒープ (通常はバイナリヒープとして実装) 用のmake_heap、push_heap、およびpop_heapアルゴリズムを提供します。イテレータを配列への参照として扱い、配列からヒープへの変換を使用します。また、これらの機能をコンテナのようなクラスにラップするコンテナアダプタpriority_queueも提供します。ただし、置換、シフトアップ/シフトダウン、またはキーの減少/増加操作に対する標準サポートはありません。
Boost C++ ライブラリにはヒープライブラリが含まれています。STL とは異なり、減少および増加操作をサポートし、追加のヒープタイプをサポートします。具体的には、d進ヒープ、二項式ヒープ、フィボナッチヒープ、ペアリングヒープ、およびスキューヒープをサポートします。
CおよびC++には、D 進ヒープとB ヒープをサポートする汎用ヒープ実装があります。STL のような API を提供します。
D プログラミング言語の標準ライブラリには、D の範囲に基づいて実装された std.container.BinaryHeap が含まれています。インスタンスは、任意のランダムアクセス範囲から構築できます。BinaryHeapは、 D の組み込みforeachステートメントによる反復処理と、std.algorithm パッケージの範囲ベースの API との統合を可能にする入力範囲インターフェイスを公開します。
HaskellにはData.Heap モジュールがあります。
Javaプラットフォーム (バージョン 1.5 以降) は、 Java Collections Frameworkのクラスでバイナリヒープ実装を提供します。このクラスはデフォルトで最小ヒープを実装します。最大ヒープを実装するには、プログラマがカスタムコンパレータを作成する必要があります。置換、シフトアップ/シフトダウン、またはキーの減少/増加操作はサポートされていません。java.util.PriorityQueue
Python には、バイナリヒープを使用して優先キューを実装する heapq モジュールがあります。ライブラリは、k ウェイマージをサポートする heapreplace 関数を公開します。
PHP には、バージョン 5.3 以降、標準 PHP ライブラリの最大ヒープ ( SplMaxHeap ) と最小ヒープ ( SplMinHeap ) の両方があります。
Perl には、CPANで入手可能なヒープ配布物の中に、バイナリ、二項式、およびフィボナッチヒープの実装があります。
Go言語には、特定のインターフェースを満たす任意の型で動作するヒープアルゴリズムを備えたヒープパッケージが含まれています。このパッケージは、置換、シフトアップ/シフトダウン、またはキーの減少/増加の操作をサポートしていません。
Apple のCore Foundationライブラリには CFBinaryHeap 構造が含まれています。
Pharo には、 Collections-Sequenceable パッケージにヒープ実装と一連のテストケースが含まれています。ヒープは、タイマーイベントループの実装で使用されます。
Rustプログラミング言語には、標準ライブラリのコレクションモジュールにバイナリ最大ヒープ実装 BinaryHeap があります。
.NET には、4 進 (d 進) 最小ヒープ実装を使用する PriorityQueue クラスがあります。これは .NET 6 から利用できます。

参照

参考文献

^ Black (ed.), Paul E. (2004-12-14). Dictionary of Algorithms and Data Structuresのheapの項目。オンライン版。米国国立標準技術研究所、2004 年 12 月 14 日。2017 年 10 月 8 日に https://xlinux.nist.gov/dads/HTML/heap.html から取得。
^ CORMEN, THOMAS H. (2009).アルゴリズム入門. アメリカ合衆国: MIT 出版局, マサチューセッツ州ケンブリッジ, イギリスロンドン. pp. 151–152. ISBN 978-0-262-03384-8。
^ ウィリアムズ、JWJ (1964)、「アルゴリズム 232 - ヒープソート」、Communications of the ACM、7 (6): 347–348、doi :10.1145/512274.512284
^ Python 標準ライブラリ、8.4。heapq — ヒープキューアルゴリズム、heapq.heappush
^ Python 標準ライブラリ、8.4。heapq — ヒープキューアルゴリズム、heapq.heappop
^ Python 標準ライブラリ、8.4。heapq — ヒープキューアルゴリズム、heapq.heapreplace
^ Suchenek, Marek A. (2012)、「Floyd のヒープ構築プログラムの基本的かつ正確な最悪ケース分析」、Fundamenta Informaticae、120 (1)、IOS Press: 75–92、doi :10.3233/FI-2012-751。
^ abcd コーメン、トーマス H. ;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。
^ abc Sleator, Daniel Dominic ; Tarjan, Robert Endre (1986 年 2 月). 「Self-Adjusting Heaps」. SIAM Journal on Computing . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN 0097-5397.
^ ab Tarjan, Robert (1983). 「3.3. 左派ヒープ」.データ構造とネットワークアルゴリズム. pp. 38–42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5。
^ 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-02-05 にオリジナル(PDF)からアーカイブ。2016-01-28に取得。
^ 「二項式ヒープ | Brilliant Math & Science Wiki」。br illiant.org 。2019年9月30日閲覧。
^ ab Brodal, Gerth Stølting; Okasaki, Chris (1996 年 11 月)、「最適な純粋機能的優先キュー」、Journal of Functional Programming、6 (6): 839–857、doi : 10.1017/s095679680000201x
^ Okasaki, Chris (1998). 「10.2. 構造的抽象化」.純粋関数型データ構造(第 1 版). pp. 158–162. ISBN 9780521631242。
^ 高岡忠雄 (1999) 2-3ヒープ理論(PDF)、p. 12
^ 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
^ Fredman, Michael Lawrence (1999 年 7 月). 「ペアリングヒープと関連データ構造の効率について」(PDF) . Journal of the Association for Computing Machinery . 46 (4): 473–501. doi :10.1145/320211.320214.
^ Pettie, Seth (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。
^ ハウプラー、ベルンハルト;セン、シッダールタ。タージャン、ロバート E. (2011 年 11 月)。「ランクペアリングヒープ」(PDF)。サイアム J. コンピューティング。40 (6): 1463–1485。土井：10.1137/100785351。
^ 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.
^ 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。
^ Brodal, Gerth S. (1996)、「最悪ケースの効率的な優先キュー」(PDF)、Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms、pp. 52–58
^ Goodrich, Michael T. ; Tamassia, Roberto (2004). 「7.3.6. ボトムアップヒープ構築」Java のデータ構造とアルゴリズム(第 3 版) pp. 338–341. ISBN 0-471-46983-1。
^ Frederickson, Greg N. (1993)、「最小ヒープにおける選択のための最適アルゴリズム」、Information and Computation (PDF)、vol. 104、Academic Press、pp. 197–214、doi : 10.1006/inco.1993.1030、2012-12-03にオリジナル(PDF)からアーカイブ、 2010-10-31取得

外部リンク

Wolfram MathWorld の Heap
基本的なヒープアルゴリズムの仕組みの説明
Bentley, Jon Louis (2000)。プログラミングパールズ(第 2 版)。Addison Wesley。pp. 147–162。ISBN 0201657880。

[8] 各挿入にはヒープの既存サイズでO(log( k )) かかります。なので、これらの挿入の定数倍（半分）は最大値の定数倍以内であり、漸近的にと仮定できます。正式には、時間はです。これはスターリングの近似からも容易にわかります。 $\sum _{k=1}^{n}O(\log k)$ $\log n/2=(\log n)-1$ $k=n$ $nO(\log n)-O(n)=O(n\log n)$

[13] ヒープ作成はn個の未ソート要素のシーケンスからヒープを構築する操作です。これはΘ ( n )時間で実行できますが、 meldはO (logn )時間で実行できます(両方の計算量が償却できる場合)。^[9]^[10]別のアルゴリズムでは、バイナリヒープに対してΘ ( n )を達成しています。^[11]

[bootstrap-meld-15] 永続ヒープ（ increase-keyをサポートしない）の場合、一般的な変換により、 meldのコストがinsertのコストまで削減されますが、 delete-maxの新しいコストは、 delete-maxとmeldの古いコストの合計になります。^[14]ここで、meld はΘ (1) 時間（挿入のコストが償却される場合は償却）で実行されますが、 delete-max は依然としてO (log n )で実行されます。これを歪んだ二項ヒープに適用すると、最悪の場合の複雑さが最適な永続ヒープである Brodal-Okasaki キューが生成されます。^[13]

[pairingdecreasekey-22] [17]の下限値、^[18]の上限値 $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$

[optimum-26] Brodal キューと厳密なフィボナッチヒープは、ヒープの最悪ケースの複雑さを最適化します。これらは、最初は命令型データ構造として説明されました。Brodal-Okasaki キューは、増加キーがサポートされていないことを除いて、同じ最適化を実現する永続的なデータ構造です。

[1] Black (ed.), Paul E. (2004-12-14). Dictionary of Algorithms and Data Structuresのheapの項目。オンライン版。米国国立標準技術研究所、2004 年 12 月 14 日。2017 年 10 月 8 日に https://xlinux.nist.gov/dads/HTML/heap.html から取得。

[2] CORMEN, THOMAS H. (2009).アルゴリズム入門. アメリカ合衆国: MIT 出版局, マサチューセッツ州ケンブリッジ, イギリスロンドン. pp. 151–152. ISBN 978-0-262-03384-8。

[3] ウィリアムズ、JWJ (1964)、「アルゴリズム 232 - ヒープソート」、Communications of the ACM、7 (6): 347–348、doi :10.1145/512274.512284

[4] Python 標準ライブラリ、8.4。heapq — ヒープキューアルゴリズム、heapq.heappush

[5] Python 標準ライブラリ、8.4。heapq — ヒープキューアルゴリズム、heapq.heappop

[6] Python 標準ライブラリ、8.4。heapq — ヒープキューアルゴリズム、heapq.heapreplace

[7] Suchenek, Marek A. (2012)、「Floyd のヒープ構築プログラムの基本的かつ正確な最悪ケース分析」、Fundamenta Informaticae、120 (1)、IOS Press: 75–92、doi :10.3233/FI-2012-751。

[CLRS-9] コーメン、トーマス H. ;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。

[sleator-tarjan-skew-10] Sleator, Daniel Dominic ; Tarjan, Robert Endre (1986 年 2 月). 「Self-Adjusting Heaps」. SIAM Journal on Computing . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN 0097-5397.

[tarjan-leftist-11] Tarjan, Robert (1983). 「3.3. 左派ヒープ」.データ構造とネットワークアルゴリズム. pp. 38–42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5。

[hayward-mcdiarmid-heap-build-12] 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-02-05 にオリジナル(PDF)からアーカイブ。2016-01-28に取得。

[14] 「二項式ヒープ | Brilliant Math & Science Wiki」。br illiant.org 。2019年9月30日閲覧。

[brodal-okasaki-16] Brodal, Gerth Stølting; Okasaki, Chris (1996 年 11 月)、「最適な純粋機能的優先キュー」、Journal of Functional Programming、6 (6): 839–857、doi : 10.1017/s095679680000201x

[17] Okasaki, Chris (1998). 「10.2. 構造的抽象化」.純粋関数型データ構造(第 1 版). pp. 158–162. ISBN 9780521631242。

[18] 高岡忠雄 (1999) 2-3ヒープ理論(PDF)、p. 12

[Iacono-19] 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

[Fredman1999-20] Fredman, Michael Lawrence (1999 年 7 月). 「ペアリングヒープと関連データ構造の効率について」(PDF) . Journal of the Association for Computing Machinery . 46 (4): 473–501. doi :10.1145/320211.320214.

[21] Pettie, Seth (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。

[23] ハウプラー、ベルンハルト;セン、シッダールタ。タージャン、ロバート E. (2011 年 11 月)。「ランクペアリングヒープ」(PDF)。サイアム J. コンピューティング。40 (6): 1463–1485。土井：10.1137/100785351。

[Fredman_And_Tarjan-24] 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.

[25] 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。

[27] Brodal, Gerth S. (1996)、「最悪ケースの効率的な優先キュー」(PDF)、Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms、pp. 52–58

[28] Goodrich, Michael T. ; Tamassia, Roberto (2004). 「7.3.6. ボトムアップヒープ構築」Java のデータ構造とアルゴリズム(第 3 版) pp. 338–341. ISBN 0-471-46983-1。

[29] Frederickson, Greg N. (1993)、「最小ヒープにおける選択のための最適アルゴリズム」、Information and Computation (PDF)、vol. 104、Academic Press、pp. 197–214、doi : 10.1006/inco.1993.1030、2012-12-03にオリジナル(PDF)からアーカイブ、 2010-10-31取得