ヒープの更新

階層的なクラスタリングにおいては、各階層で評価値が最も小さいクラスター対が統 合されるので、その統合によって影響を受ける評価値を更新する必要がある。また、 統合によってクラスター対の数は減るので、ヒープ中で対応するクラスター対を持た ない要素を削除する必要もある。

まず、ヒープ中のある要素の値の更新について考える。もし、ヒープ中のある要素 の値が元の値よりも大きな値に更新されるなら、更新後、その要素を根とする部分木 はヒープの条件を満足していない可能性がある。この場合には、上記の手続き shiftdown を用いて、その部分木がヒープの条件を満足するように要素を入れ換えれ ば、その配列は全体としてヒープの条件を満足するようになる。一方、ヒープ中のあ る要素の値が元の値よりも小さな値に更新されるなら、更新後、その要素を根とする 部分木はヒープの条件を満足しているが、ヒープを構成する木の根からその要素への 道の途中で、ヒープの条件を満足していない可能性がある。この場合には、手続き shiftdown とちょうど逆向きにその要素から木の根へ向う道に沿って、ヒープの条件 を満足するような要素の並べかえを行えば、全体としてヒープの条件を満足するよう にできる。

ヒープ中の要素 $H[s]$ を値 $x$ に更新する手続は、具体的には、図 3.9および図3.10のプログラムで実現できる。

図 3.9: ヒープの要素の値を更新するプログラム

図 3.10: 手続きshiftup

次に、ヒープ中のある要素の削除であるが、これは、その要素をヒープの最後の要素 と入替えヒープの長さを一要素分短くすれば実現できる。ヒープの最後の要素と入替 えることは、ヒープを二分木とみなした時、木の根から最も離れた葉に対応する要素 を取り除いて木を小さくすることであり、結果として、以後の要素の入替え等の手間 を少なくすることになる。

ヒープ中の要素 $H[s]$ を削除する手続きは、同様に、 shiftup と shiftdown を用いて、図3.11のプログラムで実現できる。

図 3.11: ヒープの要素を削除するプログラム

最も下の層では、ヒープの要素は、$N(N-1)/2$ 個必要であるから、ある要素の更新 および削除に必要な手間は、最悪の場合 $O(log(N))$ である。