ヒープ

ヒープ（英: heap）とは、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造の事。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多いため、そちらを参照すること。

概要

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

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

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

バリエーション

二分ヒープ

→「二分ヒープ」も参照

構造

親要素が常に2つの子要素より大きくならない（またはその逆）構造になっている。挿入、削除がO(log n)で可能。探索は $O(n)$ 。ルートが常に最小（または最大）要素となっているので、ルートの削除を繰り返すことで、ソートを行うことができる。このときの計算量は $O(n\log n)$ 。(ヒープソート)

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

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

実装

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

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

操作

探索

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

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

挿入

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

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

削除

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

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

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

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

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