ヒープ（データ構造）

Heap_(data_structure)
（低レベルのコンピュータプログラミングにおける）メモリヒープについては、
C動的メモリ割り当てを参照して
コンピュータサイエンスでは、ヒープは特殊なツリーベースのデータ構造であり、本質的にほぼ完全なツリーであり、ヒーププロパティを満たします。最大ヒープでは、任意のノードCについて、PがCの親ノードである場合、その場合、Pのキー（値）はCのキー以上です。最小ヒープでは、PのキーはCのキー以下です。「最上位」のノードヒープの（親がない）ものはルートノードと呼ばれます。
ノードキーが1〜100の整数
であるバイナリ最大ヒープの例
ヒープは、優先キューと呼ばれる抽象データ型の最も効率的な実装の1つであり、実際、優先キューは、実装方法に関係なく、「ヒープ」と呼ばれることがよくヒープでは、最高（または最低）の優先度要素が常にルートに格納されます。ただし、ヒープはソートされた構造ではありません。半順序と見なすことができます。ヒープは、最高（または最低）の優先度でオブジェクトを繰り返し削除する必要がある場合、または挿入にルートノードの削除を散在させる必要がある場合に便利なデータ構造です。
ヒープの一般的な実装は、ツリーがバイナリツリーであるバイナリヒープです（図を参照）。ヒープデータ構造、特にバイナリヒープは、ヒープソートソートアルゴリズムのデータ構造として、1964年にJWJウィリアムズによって導入されました。ヒープは、ダイクストラのアルゴリズムなどのいくつかの効率的なグラフアルゴリズムでも重要です。ヒープが完全な二分木である場合、その高さは可能な限り最小になります。つまり、N個のノードと各ノードのブランチを持つヒープの高さは常にNになります。
図に示されているように、兄弟またはいとこの間に暗黙の順序がなく、順序どおりのトラバーサルの暗黙のシーケンスがないことに注意してください（たとえば、二分探索木にあるように）。上記のヒープ関係は、ノードとその親、祖父母などの間でのみ適用されます。各ノードが持つことができる子の最大数は、ヒープのタイプによって異なります。

コンテンツ
1 オペレーション
2 実装
3 バリアント
4 バリアントの理論的限界の比較
5 アプリケーション
6 プログラミング言語の実装
7 も参照してください
8 参考文献
9 外部リンク

オペレーション
ヒープを含む一般的な操作は次のとおりです。
基本
find-max（またはfind-min）：それぞれmax-heapの最大アイテムまたはmin-heapの最小アイテムを検索します（別名peek）
挿入：ヒープに新しいキーを追加します（別名、を押します）
extract-max（またはextract-min）：ヒープから削除した後、最大ヒープから最大値のノード[または最小ヒープから最小値]を返します（別名、pop ） 。
delete-max（またはdelete-min）：それぞれ最大ヒープ（または最小ヒープ）のルートノードを削除します
置換：ルートをポップし、新しいキーを押します。バランスをとる必要があるのは2回ではなく、1回だけであり、固定サイズのヒープに適しているため、ポップの後にプッシュを実行するよりも効率的です。
創造
create-heap：空のヒープを作成します
heapify：指定された要素の配列からヒープを作成します
merge（union）：2つのヒープを結合して、両方の要素をすべて含む有効な新しいヒープを形成し、元のヒープを保持します。
meld：2つのヒープを結合して、両方の要素をすべて含む有効な新しいヒープを形成し、元のヒープを破棄します。
検査
size：ヒープ内のアイテムの数を返します。
is-empty：ヒープが空の場合はtrueを返し、それ以外の場合はfalseを返します。
内部
増加キーまたは減少キー：それぞれ最大ヒープまたは最小ヒープ内のキーを更新します
削除：任意のノードを削除します（最後のノードを移動し、ヒープを維持するためにふるいにかけます）
ふるい分け：必要な限り、ツリー内でノードを上に移動します。挿入後にヒープ状態を復元するために使用されます。ふるいのように、ノードが正しいレベルに達するまでツリーを上に移動するため、「ふるい分け」と呼ばれます。
sift-down：sift-upと同様に、ツリー内でノードを下に移動します。削除または置換後にヒープ状態を復元するために使用されます。

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

  ノードキーが1から100までの整数である完全なバイナリ最大ヒープの例と、それが配列にどのように格納されるか。
バイナリヒープの場合、配列では、最初のインデックスにルート要素が含まれます。配列の次の2つのインデックスには、ルートの子が含まれています。次の4つのインデックスには、ルートの2つの子ノードの4つの子が含まれます。したがって、インデックスiにノードがある場合、その子はインデックスに2 I + 1
{ 2i + 1}

 と2 I + 2
{ 2i + 2}

 、およびその親はインデックス⌊（i −1）/2⌋にこの単純なインデックス付けスキームにより、ツリーを「上」または「下」に移動するのが効率的になります。
ヒープのバランス調整は、ふるいにかける操作またはふるいにかける操作（順序が正しくない要素を交換する）によって行われます。追加のメモリ（ノードなど）を必要とせずに配列からヒープを構築できるため、ヒープソートを使用して配列をインプレースで並べ替えることができます。
要素がヒープに挿入またはヒープから削除された後、ヒーププロパティに違反する可能性があり、配列内の要素を交換してヒープのバランスを取り直す必要が
ヒープのタイプが異なれば、操作の実装も異なりますが、最も一般的な方法は次のとおりです。
挿入：ヒープの最後、最初に使用可能な空き領域に新しい要素を追加します。これがヒーププロパティに違反する場合は、ヒーププロパティが再確立されるまで、新しい要素をふるいにかけます（スイム操作）。
抽出：ルートを削除し、ヒープの最後の要素をルートに挿入します。これがヒーププロパティに違反する場合は、新しいルートをふるいにかけて（シンク操作）、ヒーププロパティを再確立します。
交換：ルートを削除し、新しい要素をルートに配置してふるいにかけます。抽出とそれに続く挿入と比較すると、これにより、ふるいにかけるステップが回避されます。
与えられた要素の配列からのバイナリ（またはd- ary）ヒープの構築は、古典的なフロイドアルゴリズムを使用して線形時間で実行でき、最悪の場合の比較数は2 N − 2 s 2（N）−に等しくなります。 e 2（N）（バイナリヒープの場合）。ここで、s 2（N ）はNのバイナリ表現のすべての桁の合計であり、e 2（N ）はNの主因数分解における2の指数です。これは、対数線形である元々空のヒープへの一連の連続挿入よりも高速です。

バリアント
2〜3ヒープ
Bヒープ
ビープ
バイナリヒープ
二項ヒープ
ブロダルキュー
d- aryヒープ
フィボナッチヒープ
KDヒープ
リーフヒープ
左利きのヒープ
ペアリングヒープ
基数ヒープ
ランダム化された融合可能なヒープ
スキューヒープ
ソフトヒープ
三元ヒープ Treap 弱いヒープ

バリアントの理論的限界の比較
さまざまなヒープデータ構造の時間計算量を次に示します。関数名は最大ヒープを想定しています。「 O（f）」および「Θ（f ）」の意味については、 BigO表記を参照して
手術 find-max 削除-最大
入れる
増加キー
メルド
バイナリ
Θ（1）
Θ（log  n）
O（log  n）
O（log  n）
Θ（n）
左翼 Θ（1）
Θ（log n）
Θ（log n）
O（log n）
Θ（log n）
二項
Θ（1）
Θ（log n）
Θ（1）
Θ（log n）
O（log  n）
フィボナッチ
Θ（1）
O（log  n）
Θ（1）
Θ（1）
Θ（1）
ペアリング
Θ（1）
O（log n）
Θ（1）
o（log  n）
Θ（1）
ブロダル
Θ（1）
O（log  n）
Θ（1）
Θ（1）
Θ（1）
ランクペアリング
Θ（1）
O（log n）
Θ（1）
Θ（1）
Θ（1）
厳格なフィボナッチ
Θ（1）
O（log n）
Θ（1）
Θ（1）
Θ（1）
2〜3ヒープ
O（log n）
O（log n）
O（log n）
Θ（1） ？ ^ 各挿入は、ヒープの既存のサイズでO（log（ k））を取ります。したがって、 ∑ k= 1 n O（（ ログ k ）。
{ sum _ {k = 1} ^ {n} O（ log k）}

 。以来
ログn / 2 =（（ ログ n ）。− 1
{ log n / 2 =（ log n）-1}

 、これらの挿入の定数係数（半分）は最大値の定数係数内にあるため、漸近的に仮定できます。k = n
{ k = n}

 ; 正式にはその時はn O（（ ログ n ）。− O（（ n
）。= O（（ n
ログ n ）。
{ nO（ log n）-O（n）= O（n log n）}

 。これは、スターリングの近似からも簡単に確認できます。
^ ghi 償却時間 。
^ nは、大きい方のヒープのサイズです。
^ 下界 Ω （（ ログ
ログ n ）。 { Omega（ log log n）、}

 上界と下界 O （（ 2 2 ログ
ログ
n）。 { O（2 ^ {2 { sqrt { log log n}}}）。}

  ^ BrodalとOkasakiは、サポートされていないdecrease-keyを除いて、同じ境界を持つ永続的なバリアントについて後で説明します。n個の要素を持つヒープは、 O（ n ）でボトムアップで構築できます。

アプリケーション
ヒープデータ構造には多くの用途が
ヒープソート：適切な場所にあり、2次の最悪のシナリオがない最良のソート方法の1つ。
選択アルゴリズム：ヒープを使用すると、最小要素または最大要素に一定時間でアクセスでき、ヒープ内のデータに対して他の選択（中央値またはk番目の要素など）を劣線形時間で実行できます。
グラフアルゴリズム：ヒープを内部トラバーサルデータ構造として使用することにより、実行時間は多項式の次数で短縮されます。このような問題の例としては、プリムの最小スパニングツリーアルゴリズムとダイクストラの最短経路アルゴリズムが
優先キュー：優先キューは、「リスト」や「マップ」のような抽象的な概念です。リストをリンクリストまたは配列で実装できるのと同じように、優先度付きキューはヒープまたはその他のさまざまな方法で実装できます。
K-wayマージ：ヒープデータ構造は、すでにソートされている多くの入力ストリームを単一のソートされた出力ストリームにマージするのに役立ちます。マージの必要性の例には、ログ構造化マージツリーなどの分散データからの外部ソーティングおよびストリーミング結果が含まれます。内側のループは、min要素を取得し、対応する入力ストリームの次の要素に置き換えてから、シフトダウンヒープ操作を実行します。（または、置換関数。）（優先キューのextract-max関数とinsert関数を使用すると、効率が大幅に低下します。）
順序統計量：ヒープデータ構造を使用して、配列内のk番目に小さい（または最大の）要素を効率的に見つけることができます。

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

並べ替えアルゴリズム
検索データ構造
スタック（抽象データ型）
キュー（抽象データ型）
ツリー（データ構造）
Treap、ヒープ順ツリーに基づく二分探索木の形式

参考文献
^ コルメン、トーマスH.（2009）。アルゴリズムの紹介。アメリカ合衆国：MIT Press Cambridge、Massachusetts London、England。pp。151–152。ISBN 978-0-262-03384-8。
^ Black（ed。）、Paul E.（2004-12-14）。アルゴリズムとデータ構造の辞書のヒープのエントリ。オンライン版。米国国立標準技術研究所、 2004年12月14日。2017年10月8日にhttps://xlinux.nist.gov/dads/HTML/heap.htmlから取得。
^ Williams、JWJ（1964）、 “Algorithm 232-Heapsort”、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）、「フロイドのヒープ構築プログラムの初歩的かつ正確な最悪のケースの分析」、Fundamenta Informaticae、IOS Press、120（1）：75–92、doi：10.3233 / FI-2012-751 。
^ コルメン、トーマスH .; レイザーソン、チャールズE .; リベスト、ロナルドL.（1990）。アルゴリズム入門（第1版）。MITPressとMcGraw-Hill。ISBN  0-262-03141-8。
^ 「二項ヒープ|BrilliantMath＆ScienceWiki」。brilliant.org 。
^ フレッドマン、マイケルローレンス; タージャン、ロバートE.（1987年7月）。「フィボナッチヒープと改善されたネットワーク最適化アルゴリズムでのそれらの使用」（PDF）。Journal of the Association forComputingMachinery。34（3）：596–615。CiteSeerX10.1.1.309.8927。_ 土井：10.1145/28869.28874。
  ^ Iacono、John（2000）、「ペアリングヒープの上限の改善」、Proc。アルゴリズム理論に関する第7回スカンジナビアワークショップ（PDF）、コンピュータサイエンスのレクチャーノート、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 ^ フレッドマン、マイケルローレンス（1999年7月）。「ペアリングヒープと関連データ構造の効率について」（PDF）。Journal of the Association forComputingMachinery。46（4）：473–501。土井：10.1145/320211.320214。
^ ペティー、セス（2005）。ペアリングヒープの最終分析に向けて（PDF）。FOCS’05コンピュータサイエンスの基礎に関する第46回IEEEシンポジウムの議事録。pp。174–183。CiteSeerX10.1.1.549.471。_ 土井：10.1109/SFCS.2005.75。ISBN
  0-7695-2468-0。
^ Brodal、Gerth S.（1996）、「最悪の場合の効率的な優先度付きキュー」（PDF）、Proc。離散アルゴリズムに関する第7回ACM-SIAMシンポジウム、 52〜58ページ
^ グッドリッチ、マイケルT .; タマシア、ロベルト（2004）。「7.3.6。ボトムアップヒープ構造」。Javaのデータ構造とアルゴリズム（第3版）。pp。338–341。ISBN  0-471-46983-1。
^ Haeupler、Bernhard; セン、シッダールタ; Tarjan、Robert E.。「ランクペアリングヒープ」（PDF）。SIAMJ.コンピューティング。40（6）：1463–1485。土井：10.1137/100785351。
^ Brodal、GerthStølting ; Lagogiannis、ジョージ; Tarjan、Robert E.（2012）。厳密なフィボナッチヒープ（PDF）。コンピューティング理論に関する第44回シンポジウムの議事録-STOC’12。pp。1177–1184。CiteSeerX10.1.1.233.1740。_ 土井：10.1145/2213977.2214082。ISBN
  978-1-4503-1245-5。
^ 高岡忠夫（1999）、2–3ヒープの理論（PDF）、p。12
^ Frederickson、Greg N.（1993）、「最小ヒープでの選択のための最適なアルゴリズム」、情報と計算（PDF）、vol。104、Academic Press、pp。197–214、doi：10.1006 / inco.1993.1030、2012-12-03にオリジナル（PDF）からアーカイブ、2010-10-31を取得

外部リンク
コモンズには、ヒープデータ構造に関連するメディアが
ウィキブックスのデータ構造には、次のトピックに関するページが最小ヒープと最大ヒープ
WolframMathWorldのヒープ
基本的なヒープアルゴリズムがどのように機能するかの説明
ベントレー、ジョンルイス（2000）。プログラミングパール（第2版）。アディソンウェスリー。pp。147–162。ISBN 0201657880。”