階層的なクラスタリングでは、各階層で評価値が最小のクラスター対を見つけて、そ
れらを統合することを繰返し、最終的な分類結果を得る。ある階層でのクラスターの
数を とすると、単純な探索方法では評価値が最小のクラスター対を見つけるた
めに
の手間が必要となる。ここでは、各クラスター対の評価をヒープ
に蓄えることによりこの手間を減らすことを考える。
今、各クラスター対の評価値を蓄えたヒープがすでに作られているとすると、最小の
評価値を持つクラスター対は、ヒープの第1番目の要素 に対応するクラスター
対である。従って、最小の評価値を持つクラスター対を見つける手間はかからない。
また、各階層でのクラスター対の統合によって影響を受ける評価値は、統合されるク
ラスターに関係するもののみであるから、ヒープはクラスタリングの前に一度作れば、
あとは、各階層で統合されるクラスターに関係する要素のみを修正すればよいことに
なる。ただし、統合によって影響を受けるクラスター対の評価値を修正するためには、
各クラスター対の評価値がヒープのどの要素に蓄えられているかの情報とヒープの各
要素がどのクラスター対の評価値を蓄えているかの情報が必要となる。ここでは、そ
うした情報を配列 Where および Pair に蓄えることにする。