next up previous
次へ: ヒープの更新 上へ: ヒープを用いた階層的クラスタリングアルゴリズム 戻る: ヒープを用いた階層的クラスタリングアルゴリズム

ヒープの構成

分類対象の数を $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: ヒープを構成するプログラム
\begin{figure}{\tt\small\begin{tabbing}
1234567890\=1234567890\=1234567890\=1234...
...; shiftdown(H,l,r,Where,Pair); \\
\> \}
\end{tabbing}\normalsize}
\end{figure}

図 3.8: 手続きshiftdown
\begin{figure}{\tt\small\begin{tabbing}
1234567890\=1234567890\=1234567890\=1234...
... = x; Where[p] = i; Pair[i]=p; \\
\> \}
\end{tabbing}\normalsize}
\end{figure}

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



Takio Kurita 平成14年7月3日