二分ヒープ
二分ヒープ(にぶんヒープ,バイナリヒープ,Binary heap)とは、二分木を使って作られるヒープ(データ構造)の特に単純な種類のひとつである。それは、二分木に、以下の2つの制約を追加したものとみなせる。
要素間の順序関係に従った比較によって、各々のノードはそのノードの子よりも大きいか等しくなるように配置される(heap property)
木は完全にバランスの取れた二分木(すべての葉は同じ高さにある)になるか、木のもっとも高い方がすべて埋まっていないならば、ノードは左から右へ順に埋まっていく(shape property)
ここで「より大きい」とは、比較のためにいかなる比較関数を選択するかによって意味づけられる。ノード内のデータが常に数値であるとは限らないので、数量的な『より大きい』である必要はなく、数理的に言うところの全順序であればよい。
また、heap propertyのような制約を持つ木を一般に「部分順序付き木」と言う。ヒープは、部分順序付き二分木に、さらにshape propertyの制約を加えたものである。配列を使って実装できるという特性がある(後述)。
比較が数量的な「より大きい」であるヒープは最大ヒープ (max heap) と呼ばれる。また、比較が数量的な「より小さい」であるヒープは最小ヒープ (min heap) と呼ばれる。たとえば優先順位付き待ち行列において、小さい値が高い優先度を意味するのであれば、最小ヒープを使う。
ヒープ内の子同士の順序は、heap propertyによって特定できないことに注意すること。つまり、親を同じくする二つの子は、制約を壊さない限り自由に入れ替えることができる(Treapと比較せよ)。
親は floor(n / 2) (※多くの処理系で、整数除算として単に n / 2 で実装できる)
兄弟(ないし同世代) n + 1, n - 1
この規則性により、ほとんど完全な二分木は、ポインタ用のメモリを必要とせず、(可変長の)配列に、たいへん効率よく詰め込むことができ、また要素を辿ることもできる。これは暗黙のデータ構造の一つの単純な例である。
このやり方は、ヒープソートで特に役に立つ。入力の配列を、ヒープを格納するために再利用し、in-place なソートが実現できるからである。
0 からの番号付けだと、式が少し複雑になるので、1 からの番号付けが一般に使われる。C言語など、配列が 0 始まりの場合には、配列の 0 番目を、「ルートのルート」と言われるような手法のための番兵のデータを置いたり、そのヒープ木の現在の要素数の格納などに流用することがある。 二分ヒープ木のマージは、等しいサイズのヒープ2個の場合、Θ(n)だけかかる。マージ処理がよく使われる処理であるならば、二項ヒープのような違うヒープ実装を推奨する。