ヒープ（データ構造）

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

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

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

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

ヒープは通常、要素が格納されている配列と同じ場所にインプレースで構築され、その構造は操作のアクセスパターンに暗黙的に組み込まれます。ヒープは、基数木など、理論上の限界が類似している、あるいは場合によってはより優れている他のデータ構造とは異なり、キーを格納するために使用されるメモリ以外に追加のメモリを必要としません。

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

基本

• find-max（またはfind-min）：最大ヒープの最大要素、または最小ヒープの最小要素をそれぞれ見つけます（別名peek）。
• insert : ヒープに新しいキーを追加する (別名push ^{[ 4 ]} )
• extract-max (またはextract-min ): ヒープから削除した後 (別名pop ^{[ 5 ]} ) 、最大ヒープから最大値のノード (または最小ヒープから最小値) を返します。
• delete-max (またはdelete-min ): 最大ヒープ (または最小ヒープ) のルートノードをそれぞれ削除します。
• replace : ルートをポップして新しいキーをプッシュします。これは、ポップしてからプッシュするよりも効率的です。バランス調整を2回ではなく1回だけ行う必要があり、固定サイズのヒープに適しています。^{[ 6 ]}

創造

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

検査

• size : ヒープ内のアイテム数を返します。
• is-empty : ヒープが空の場合は true を返し、そうでない場合は false を返します。

内部

• increase-keyまたはdecrease-key : それぞれ最大ヒープまたは最小ヒープ内のキーを更新する
• delete：任意のノードを削除します（その後、最後のノードを移動し、ヒープを維持するためにふるい分けを行います）。
• sift-up：必要なだけツリー内のノードを上に移動します。挿入後にヒープの状態を復元するために使用されます。ノードがふるいのように正しいレベルに到達するまでツリーを上に移動するため、「sift」と呼ばれます。
• sift-down：ノードをツリー内で下に移動させます。sift-upと同様です。削除または置換後にヒープの状態を復元するために使用されます。

ヒープは通常、以下のように配列を用いて実装されます。

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

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

ヒープのバランス調整は、要素の順不同交換（シフトアップまたはシフトダウン）によって行われます。ヒープは、ノードなどの追加メモリを必要とせずに配列から構築できるため、ヒープソートを使用して配列をその場でソートできます。

ヒープに要素が挿入または削除された後、ヒープの特性が損なわれる可能性があり、配列内の要素を交換することによってヒープのバランスを再調整する必要があります。

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

• 挿入：新しい要素をヒープの末尾の、最初に利用可能な空きスペースに追加します。これがヒープの性質に違反する場合は、ヒープの性質が回復するまで新しい要素を上に移動させます（スイム操作）。
• 抽出：ルートを削除し、ヒープの最後の要素をルートに挿入します。これによりヒープの性質が損なわれる場合は、新しいルートを下にずらす（シンク操作）ことでヒープの性質を再確立します。
• 置換：根を取り除き、新しい要素を根に挿入してふるいにかける。抽出後に挿入する場合と比較すると、ふるいにかける工程が不要になる。

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

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

ヒープデータ構造には多くの応用例がある。

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

• C ++ 標準ライブラリは、ヒープ (通常はバイナリヒープとして実装) 用のmake_heap、push_heap、pop_heapアルゴリズムを提供しており、これらは任意のランダムアクセスイテレータに対して動作します。イテレータは配列への参照として扱われ、配列からヒープへの変換が使用されます。また、これらの機能をコンテナのようなクラスでラップするstd::priority_queueクラスも提供されています。ただし、replace、sift-up/sift-down、decrease/increase-key 操作は標準ではサポートされていません。
• Boost C++ライブラリにはヒープライブラリ^{[ 25 ]}が含まれています。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コレクションフレームワークjava.util.PriorityQueueのクラスを使用してバイナリヒープの実装を提供しています。このクラスはデフォルトで最小ヒープを実装します。最大ヒープを実装するには、プログラマがカスタムコンパレータを作成する必要があります。置換、シフトアップ/シフトダウン、キーの減少/増加操作はサポートされていません。
• Pythonには、二分ヒープを用いて優先度付きキューを実装するheapqモジュールがあります。このライブラリは、kウェイマージをサポートするheapreplace関数を提供しています。
• PHP の標準ライブラリには、バージョン 5.3 以降、最大ヒープ ( SplMaxHeap ) と最小ヒープ ( SplMinHeap ) の両方が含まれています。
• Perl には、 CPANで入手可能なHeapディストリビューションに、バイナリ、二項式、フィボナッチ ヒープの実装が含まれています。
• Go言語には、指定されたインターフェースを満たす任意の型に対して動作するヒープアルゴリズムを含むheapパッケージがあります。ただし、このパッケージは置換、シフトアップ/シフトダウン、またはキーの減少/増加操作をサポートしていません。
• AppleのCore Foundationライブラリには、CFBinaryHeap構造体が含まれています。
• Pharoには、Collections-Sequenceableパッケージにヒープの実装と一連のテストケースが含まれています。ヒープはタイマーイベントループの実装で使用されます。
• Rustプログラミング言語には、標準ライブラリのcollectionsモジュールに、バイナリ最大ヒープの実装であるBinaryHeapが用意されています。
• .NETには、四元（d進）最小ヒープ実装を使用するPriorityQueueクラスがあります。これは.NET 6以降で利用可能です。

• ソートアルゴリズム
• 検索データ構造
• Treapは、ヒープ順序付けされた木に基づく二分探索木の一種である。

• Wolfram MathWorldのHeap
• 基本的なヒープアルゴリズムの仕組みの説明
• ベントレー、ジョン・ルイス（2000）。プログラミング・パールズ（第2 版）。アディソン・ウェスリー。147 ～ 162ページ。ISBN  0201657880。