ヒープ（データ構造）
ノードキーが1から100までの整数であるバイナリ最大ヒープの例

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

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

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

図に示されているように、兄弟やいとこ同士の間には暗黙的な順序関係はなく、また、例えば二分探索木のような順序探索の順序関係も暗黙的にはありません。上述のヒープ関係は、ノードとその親（祖父母）の間にのみ適用されます。各ノードが持つことができる子ノードの最大数は、ヒープの種類によって異なります。

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

オペレーション

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

基本
  • 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 を返します。
内部
  • increase-keyまたはdecrease-key : それぞれ最大ヒープまたは最小ヒープ内のキーを更新する
  • delete : 任意のノードを削除します（その後、最後のノードを移動し、ヒープを維持するためにふるいにかけます）
  • sift-up : 必要なだけツリー内のノードを上に移動します。挿入後にヒープの状態を復元するために使用されます。ノードが適切なレベルに達するまでツリーを上方に移動するため、「sift」と呼ばれます。これは、ふるいのように機能します。
  • sift-down : sift-up と同様にツリー内のノードを下に移動します。削除または置き換え後にヒープ状態を復元するために使用されます。

配列を使用した実装

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

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

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

ヒープのバランス調整は、シフトアップまたはシフトダウン操作（順序がずれている要素の入れ替え）によって行われます。配列からヒープを構築する際に、追加のメモリ（例えばノード用）を必要とせずに済むため、ヒープソートは配列をインプレースでソートするために使用できます。

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

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

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

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

変種

変異体の理論的限界の比較

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

手術 最大値を見つける 削除最大数 増加キー 入れる 融合する ヒープを作る[ b ]
バイナリ[ 8 ]Θ (1) Θ (log  n ) Θ (log  n ) Θ (log  n ) Θ ( n ) Θ ( n )
スキュー[ 9 ]Θ (1) O (log  n )午前。O (log  n )午前。O (log  n )午前。O (log  n )午前。Θ ( n )午前。
左翼[ 10 ]Θ (1) Θ (log  n ) Θ (log  n ) Θ (log  n ) Θ (log  n ) Θ ( n )
二項分布[ 8 ] [ 12 ]Θ (1) Θ (log  n ) Θ (log  n ) Θ（１）午前。Θ (log  n ) [ c ]Θ ( n )
歪んだ二項分布[ 13 ]Θ (1) Θ (log  n ) Θ (log  n ) Θ (1) Θ (log  n ) [ c ]Θ ( n )
2～3山[ 15 ]Θ (1) O (log  n )午前。Θ (1) Θ（１）午前。O (log  n ) [ c ]Θ ( n )
ボトムアップの歪み[ 9 ]Θ (1) O (log  n )午前。O (log  n )午前。Θ（１）午前。Θ（１）午前。Θ ( n )午前。
ペアリング[ 16 ]Θ (1) O (log  n )午前。o (log  n )午前。[ d ]Θ (1) Θ (1) Θ ( n )
ランクペアリング[ 19 ]Θ (1) O (log  n )午前。Θ（１）午前。Θ (1) Θ (1) Θ ( n )
フィボナッチ[ 8 ] [ 20 ]Θ (1) O (log  n )午前。Θ（１）午前。Θ (1) Θ (1) Θ ( n )
厳密なフィボナッチ[ 21 ] [ e ]Θ (1) Θ (log  n ) Θ (1) Θ (1) Θ (1) Θ ( n )
ブロダル[ 22 ] [ e ]Θ (1) Θ (log  n ) Θ (1) Θ (1) Θ (1) Θ ( n ) [ 23 ]
  1. ^各挿入はヒープの既存サイズをO(log( k )) 占有するため、 となります。 であるため、これらの挿入の定数倍（半分）は最大値の定数倍以内であるため、漸近的に と仮定できます。正式には、時間は です。これはスターリングの近似からも容易にわかります。∑け＝1nお（ログ⁡け）{\displaystyle \sum _{k=1}^{n}O(\log k)}ログ⁡n/2＝（ログ⁡n）−1{\displaystyle \log n/2=(\log n)-1}け＝n{\displaystyle k=n}nお（ログ⁡n）−お（n）＝お（nログ⁡n）{\displaystyle nO(\log n)-O(n)=O(n\log n)}
  2. ^ make-heap は、 n個の未ソート要素のシーケンスからヒープを構築する操作である。meldがO (log  n ) 時間で実行されるのに対し、make-heap はΘ ( n ) 時間で実行できる（ただし、両方の計算量は償却可能である）。 [ 9 ] [ 10 ]二分ヒープに対してΘ ( n )時間を達成する別のアルゴリズムがある。 [ 11 ]
  3. ^ a b c永続ヒープ（ increase-keyをサポートしない）の場合、一般的な変換により、meldのコストがinsertのコストまで削減されます。delete -maxの新しいコストは、 delete-maxとmeldの古いコストの合計になります。[ 14 ]ここで、meldはΘ (1)時間（挿入のコストが償却される場合）で実行されますが、 delete-maxは依然としてO（log  n）で実行されます。これを歪んだ二項ヒープに適用すると、最悪のケースの複雑さが最適な永続ヒープであるBrodal-Okasakiキューが生成されます。[ 13 ]
  4. ^ [ 17 ]の下限値[ 18 ]の上限値Ω（ログ⁡ログ⁡n）、{\displaystyle \Omega (\log \log n),}お（22ログ⁡ログ⁡n）。{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}
  5. ^ a b Brodalキューと厳密なフィボナッチヒープは、ヒープの最悪ケース計算量を最適化する。これらは当初、命令型データ構造として記述された。Brodal-Okasakiキューは、増加キーがサポートされていないことを除いて、同様の最適化を実現する永続的データ構造である。

アプリケーション

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

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

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

  • C ++標準ライブラリは、ヒープ（通常はバイナリヒープとして実装）に対して、任意のランダムアクセスイテレータを操作するmake_heap、push_heap、pop_heapアルゴリズムを提供しています。これらのアルゴリズムは、イテレータを配列への参照として扱い、配列からヒープへの変換を行います。また、これらの機能をコンテナのようなクラスでラップするstd::priority_queueクラスも提供しています。ただし、置換、シフトアップ/シフトダウン、キーの減少/増加といった操作は標準でサポートされていません。
  • Boost C++ライブラリにはヒープライブラリが含まれています。STLとは異なり、減少演算と増加演算をサポートし、追加のヒープタイプ（具体的には、d進ヒープ、二項式ヒープ、フィボナッチヒープ、ペアリングヒープ、スキューヒープ）をサポートしています。
  • CおよびC++用の汎用ヒープ実装があり、D-aryヒープとB-heapをサポートしています。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-way マージをサポートする heapreplace 関数を公開しています。
  • PHP には、標準 PHP ライブラリのバージョン 5.3 以降、最大ヒープ ( SplMaxHeap ) と最小ヒープ ( SplMinHeap ) の両方があります。
  • Perl には、 CPANで入手可能なヒープ配布物の中にバイナリ、二項式、およびフィボナッチ ヒープの実装があります。
  • Go言語には、指定されたインターフェースを満たす任意の型を操作するヒープアルゴリズムを備えたヒープパッケージが含まれています。このパッケージは、置換、シフトアップ/シフトダウン、キーの減少/増加といった操作をサポートしていません。
  • Apple のCore FoundationライブラリにはCFBinaryHeap構造が含まれています。
  • Pharoには、Collections-Sequenceableパッケージにヒープ実装と一連のテストケースが含まれています。ヒープはタイマーイベントループの実装で使用されます。
  • Rustプログラミング言語には、標準ライブラリのコレクションモジュールにバイナリ最大ヒープ実装BinaryHeapがあります。
  • .NETには、4値（d値）最小ヒープ実装を使用するPriorityQueueクラスがあります。これは.NET 6から利用可能です。

参照

参考文献

  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. ^ Williams, 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。
  8. ^ a b c dコーメン、トーマス H. ;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。
  9. ^ a b c 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 .  
  10. ^ a b Tarjan, Robert (1983). 「3.3. 左派ヒープ」.データ構造とネットワークアルゴリズム. pp.  38– 42. doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5。
  11. ^ 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日閲覧。 
  12. ^ 「二項式ヒープ | Brilliant Math & Science Wiki」brilliant.org . 2019年9月30日閲覧。
  13. ^ a b Brodal, Gerth Stølting; Okasaki, Chris (1996年11月)、「最適な純粋機能的優先度キュー」、Journal of Functional Programming、6 (6): 839– 857、doi : 10.1017/s095679680000201x
  14. ^ Okasaki, Chris (1998). 「10.2. 構造的抽象化」.純粋関数型データ構造（第1版）. pp.  158– 162. ISBN 9780521631242。
  15. ^高岡忠雄(1999) 「2-3ヒープ理論」 (PDF)、p.12
  16. ^ 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
  17. ^ Fredman, Michael Lawrence (1999年7月). 「ペアリングヒープと関連データ構造の効率について」(PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .
  18. ^ペティ, セス (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。
  19. ^ハウプラー、ベルンハルト;セン、シッダールタ。タージャン、ロバート E. (2011 年 11 月) 「ランクペアリングヒープ」(PDF)。サイアム J. コンピューティング。40 (6): 1463 ～ 1485 年。土井: 10.1137/100785351。
  20. ^ 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 . 
  21. ^ 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。
  22. ^ Brodal, Gerth S. (1996)、「最悪ケースの効率的な優先キュー」（PDF）、第7回ACM-SIAM離散アルゴリズムシンポジウム論文集、pp.  52– 58
  23. ^ Goodrich, Michael T. ; Tamassia, Roberto (2004). 「7.3.6. ボトムアップヒープ構築」. 『Javaにおけるデータ構造とアルゴリズム』（第3版）. pp.  338– 341. ISBN 0-471-46983-1。
  24. ^ Frederickson, Greg N. (1993), "An Optimal Algorithm for Selection in a Min-Heap", Information and Computation (PDF) , vol. 104, Academic Press, pp.  197– 214, doi : 10.1006/inco.1993.1030 , 2012年12月3日時点のオリジナル(PDF)からアーカイブ, 2010年10月31日取得
ウィキメディア コモンズには、ヒープ データ構造に関連するメディアがあります。
ウィキブックのデータ構造には、最小ヒープと最大ヒープに関するページがあります。
  • Wolfram MathWorldのHeap
  • 基本的なヒープアルゴリズムの仕組みの説明
  • ベントレー、ジョン・ルイス (2000). 『プログラミング・パールズ』（第2版）. アディソン・ウェスレー. pp.  147– 162. ISBN 0201657880。
「 https://en.wikipedia.org/w/index.php?title=Heap_(data_structure)&oldid=1325128534」から取得