二分ヒープ
Channel: 宇宙のすべての知識 プリンシピア
Date: 24/01/2020

二分ヒープ, by Wikipedia https://ja.wikipedia.org/wiki?curid=557352 / CC BY SA 3.0

#二分木
#ヒープ
#数学に関する記事
二分ヒープ

二分ヒープ（にぶんヒープ,バイナリヒープ,Binary heap）とは、二分木を使って作られるヒープ(データ構造)の特に単純な種類のひとつである。それは、二分木に、以下の2つの制約を追加したものとみなせる。


ここで「より大きい」とは、比較のためにいかなる比較関数を選択するかによって意味づけられる。ノード内のデータが常に数値であるとは限らないので、数量的な『より大きい』である必要はなく、数理的に言うところの全順序であればよい。

また、heap propertyのような制約を持つ木を一般に「部分順序付き木」と言う。ヒープは、部分順序付き二分木に、さらにshape propertyの制約を加えたものである。配列を使って実装できるという特性がある（後述）。

比較が数量的な「より大きい」であるヒープは最大ヒープ (max heap) と呼ばれる。また、比較が数量的な「より小さい」であるヒープは最小ヒープ (min heap) と呼ばれる。たとえば優先順位付き待ち行列において、小さい値が高い優先度を意味するのであれば、最小ヒープを使う。

ヒープ内の子同士の順序は、heap propertyによって特定できないことに注意すること。つまり、親を同じくする二つの子は、制約を壊さない限り自由に入れ替えることができる（Treapと比較せよ）。

すでに存在しているヒープに、前述の制約を保ったまま要素を追加するには、up-heap（bubble-up, percolate-up, sift-up, trickle-up, heapify-up, cascade-up 等とも）と呼ばれる操作によらなければならない。以下のアルゴリズムにしたがって、二分ヒープに対し O(log n) で操作を行うことができる。


我々は、この操作をツリー上で最大各々の深さで行う必要がある。つまり、木の高さ分行う必要があるので、O(log n) かかる。しかしながら、およそ要素の50%が葉であり最下層から2レベルまでには75%の要素が含まれることから、新しい要素を挿入する際、ヒープを維持するために、上向きに2, 3レベル動かすくらいですむだろう。このように、二分ヒープは、要素の挿入には平均 O(1) の固定時間をサポートする。

我々が最大ヒープと呼んでいるものは以下のようなものである。

ここで、ヒープに「15」という数字を付け加えたい。まず最初に X の印がついている場所に「15」を置く。しかし、「15」は親である「8」より大きいのでヒープの制約条件に違反している。そこで、「15」と「8」を入れ替える。最初の入れ替え後、ヒープは以下の様になる。

しかし「15」はその親である「11」よりも大きいので、まだヒープの制約条件に違反している。そこで、再度入れ替える必要がある。

これで、適切な最大ヒープができた。

ヒープからルートを削除する手順、つまり効果的に最大ヒープ内で最大要素を検索したり最小ヒープから最小要素を検索する手順は、up-heap とよく似ている。これを down-heap (bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down) と呼ぶ。ルートを削除するということは、ルートを木の末端の要素と入れ替えることである。前と同じ最大ヒープを例にとると、

「11」を削除して「4」と入れ替える。

親である「4」は子である「8」よりも小さいのでヒープの制約条件に違反している。この2つの要素を交換すればヒープの制約条件は保たれ(「4」はより大きい子と交換される。最小ヒープならばより小さい子と交換される)、これ以上操作の必要はない。

木構造を配列で管理している場合は、ノード → 配列番地への管理が別途必要である。これは連想配列でもできるし、ノードに持たせても良いし、現れるノードが決まっているのなら普通の配列でも管理できる。

その上で手順は以下の通り。

値の更新は例えばダイクストラ法やA*などで使用する。最大ヒープの場合、ノードの値を更新した後、値が増えるなら up-heap し、値が減るなら down-heap すれば良い。計算量は増えるが、削除して追加でも実装可能。

平均計算量だけでなく、最悪計算量も O(1) にしたい場合は、他のヒープ構造を検討するべきだが、二分ヒープを配列で実装した場合、計算量の定数項分が、一般的に他のアルゴリズ...