ヒープのソースを表示

{{otheruses|木構造の1つ|メモリ領域|ヒープ領域}}
'''ヒープ'''（{{lang-en-short|heap}}）とは、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ[[木構造 (データ構造)|木構造]]の事。単に「ヒープ」という場合、[[二分木]]を使った[[二分ヒープ]]を指すことが多いため、そちらを参照すること。

[[画像:Binary heap indexing.png|thumb|right|二分ヒープのインデックス付け]]

==概要==
ヒープは最小値（または最大値）を求めるのに適した木構造の一種であり、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ。子要素が複数ある場合、子要素間の大小関係に制約はない。

[[フィボナッチヒープ]]の場合、挿入や最小値検索やマージが一定償却時間で行え、削除は<math alt="O(log n)">O(\log n)</math>で行える。

[[優先度付きキュー]]の実装としても使われる。[[プリム法]]や[[ダイクストラ法]]などのグラフ問題のアルゴリズムでも使われている。

==バリエーション==
*[[二分ヒープ]] (バイナリヒープ)
*[[二項ヒープ]]
*[[フィボナッチヒープ]]
*[[:en:2-3 heap|2-3 heap]]
*[[:en:Beap|Beap]]
*[[:en:D-ary heap|D-ary heap]]
*[[:en:Leftist heap|Leftist heap]]
*[[:en:Pairing heap|Pairing heap]]
*[[:en:Skew heap|Skew heap]]
*[[:en:Soft heap|Soft heap]]
*[[:en:Ternary heap|Ternary heap]]

==二分ヒープ==
{{See also|二分ヒープ}}

===構造===
親要素が常に2つの子要素より大きくならない（またはその逆）構造になっている。
挿入、削除が[[ランダウの記号|''O'']](log ''n'')で可能。探索は<math alt="O(n)">O(n)</math>。
ルートが常に最小（または最大）要素となっているので、ルートの削除を繰り返すことで、[[ソート]]を行うことができる。
このときの計算量は<math alt="O(n log n)">O(n \log n)</math>。([[ヒープソート]])

木の高さの低い方（または深さの浅い方）から、また同じ高さでも左または右のどちらかに要素を寄せた木構造を作る。深さ <math alt="n">n</math> の要素がすべて使われるまで、深さ <math alt="n+1">n+1</math> の要素は作成しない。要素の添字を 1 から開始すると、要素 <math alt="n">n</math> の親は <math alt="n/2">n\div2</math>、子は <math alt="2n">2n</math> および <math alt="2n+1">2n+1</math> となる（添字を 0 から開始すると親は <math alt="(n-1)/2">(n-1)\div2</math>、子は <math alt="2n+1">2n+1</math> と <math alt="2n+2">2n+2</math> である）。

後述する手順に従って操作すれば、データの出現順序に関わらず、このような構造を容易に維持できることがヒープの利点である。

===実装===

構造の節で述べたように、任意の要素に対する親要素と子要素は添字の計算で特定することができる。また要素が存在するか否かは、全要素数と比較することで判断できる。このため[[ポインタ (プログラミング)|ポインタ]] に相当するデータを持たなくても、データ自体を格納した[[配列]]だけでヒープ構造を実装することが可能である。

ただし個々の要素のデータ容量が大きい場合は、要素の入れ替えにおけるコピー処理の負荷が問題になる場合もある。対策として、敢えて各要素へのポインタ（あるいは各要素の添字）からなる配列を別に作成して、この配列でヒープ構造を実装するという選択も考えられる。

===操作===

====探索====

ヒープ構造では子要素間の大小関係に制約がないため、目的とする要素が見つかるまで全要素を順に調べる必要がある。したがって、任意のデータを探索する必要がある場合にヒープ構造を使うことは勧められない。

ただし、ルートに最小（または最大）の要素が来ることは保証されている。これを利用してソートを行うアルゴリズムが[[ヒープソート]]である。

====挿入====

子は親より大きいか等しく、添字は 1 から開始するものとして記述する。また、木全体の要素数を <math alt="N">N</math> とする。

# 操作対象の要素 <math alt="n=N+1">n=N+1</math> とし、追加する要素を <math alt="n">n</math> に置く。
# 要素 <math alt="n">n</math> を親（<math alt="n/2">n\div2</math>）と比較する。要素 <math alt="n">n</math> がルート（<math alt="n=1">n=1</math>）か、または比較結果が親以上なら終了。
# 親の方が大きければ親子を入れ替え、<math alt="n=n/2">n = n\div2</math> として繰り返す。

====削除====
子は親より大きいか等しく、添字は 1 から開始するものとして記述する。また、木全体の要素数を <math alt="N">N</math> とする。
ルートを削除する手順は以下のとおりである。

# 操作対象の要素 <math alt="n=1">n=1</math> とし、要素 <math alt="N">N</math> を 1（ルート）に移動する。
# 要素 <math alt="n">n</math> を子（<math alt="2n">2n</math> および <math alt="2n+1">2n+1</math>）と比較する。子が存在しない（<math alt="2n&gt;">2n>N</math>）か、またはすべての子の比較結果が要素 <math alt="n">n</math> 以上なら終了。
# 小さいほうの子と要素 <math alt="n">n</math> を入れ替え、<math alt="n">n</math> を入れ替えた子の添字として繰り返す。

ルート以外を削除する場合も、要素 <math alt="N">N</math> を削除箇所に移動するところまでは同じである。
ただし、その後の操作は以下の条件分岐が必要になる。

; 要素 N &gt; 子要素の場合 : ルートの削除と同様に、葉に向かって入れ替え操作を繰り返す
; 要素 N &lt; 親要素の場合 : 挿入時と同様に、ルートに向かって入れ替え操作を繰り返す

なお削除前に正しいヒープ構造になっていれば、親要素 ≤ 子要素なので、両方が同時に成り立つことはない。

{{データ構造}}

{{デフォルトソート:ひいふ}}
[[Category:データ構造]]
[[Category:ヒープ|*]]