分類対象の数を とすると、各対象をひとつのクラスターとみなす 最も下の階層では、クラスター対の総数は 個である。 従って、 個の要素を持つヒープを構成する必要がある。
今、配列 に任意の順番でクラスター対の評価値が代入されてい るとする。この時、要素 に対しては、 あるいは となるような添え字は存在しないので、これらの要素はすでにヒー プの条件を満足している。従って、残りの要素 が、ヒープの 条件を満足するように要素を並べかえればヒープが構成できる。ヒープの条件を満足 するような要素の並べかえは、ヒープを二分木とみなした時の木の道にそって要素を 入れ替える手続 shiftdown を用いて簡単に実現できる[179]。
具体的には、図3.7および図3.8のプログラムで、ヒープが 構成できる。
ヒープを構成するための手間は、 個のクラスター対に対して、高々 である。