ヒープの構成

分類対象の数を $N$ とすると、各対象をひとつのクラスターとみなす 最も下の階層では、クラスター対の総数は $N(N-1)/2$ 個である。 従って、$M=N(N-1)/2$ 個の要素を持つヒープを構成する必要がある。

今、配列 $H[1] \ldots H[M]$ に任意の順番でクラスター対の評価値が代入されてい るとする。この時、要素 $H[M/2] \ldots H[M]$ に対しては、$j=2i$ あるいは $j=2i+1 (i < j)$ となるような添え字は存在しないので、これらの要素はすでにヒー プの条件を満足している。従って、残りの要素 $H[1] \ldots H[N/2]$ が、ヒープの 条件を満足するように要素を並べかえればヒープが構成できる。ヒープの条件を満足 するような要素の並べかえは、ヒープを二分木とみなした時の木の道にそって要素を 入れ替える手続 shiftdown を用いて簡単に実現できる[179]。

具体的には、図3.7および図3.8のプログラムで、ヒープが 構成できる。

図 3.7: ヒープを構成するプログラム

図 3.8: 手続きshiftdown

ヒープを構成するための手間は、$M=N(N-1)/2$ 個のクラスター対に対して、高々 $O(N^2\log(N))$ である。