(9.1.1) ヒープソートに登場する「ヒープ (heap)」は 「木」と呼ばれるデータ型の一種である。 一般の木を扱う方法はこの授業では取りあげない。 また，ヒープという言葉はコンピュータの世界ではこれ以外にもいろいろな意味で使われる。
(9.1.2) ヒープソートでは， 配列 a[1], ..., a[N] において， 「a[2*i] と a[2*i+1] は a[i] の子」 と考える。 「a[i] は a[2*i] と a[2*i+1] の親」 となる。
(9.1.3) 次のような図を書いて考えるとわかりやすい。
a[1]
a[2] a[3]
a[4] a[5] a[6] a[7]
a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15]
N の値によっては， この山から右下の一部が欠けたものになる。
(9.1.4) 上の例の“高さ”が 3 であるか 4 であるかは定義のしかたの問題だが， いずれにせよ，ほぼ log(N) である。 （(8.4.2) に書いたように，対数の底は 2 である。）
(9.1.5) 「a[i] から a[j] までがヒープである」 とは， a[i], a[i+1], ..., a[j] のうちで親子関係にある全てのペアについて，親が子以上であることをいう。
(9.1.6) 補題： a[i+1] から a[r] までがヒープになっているとき， a[i] から a[r] までの要素の間で Ο(log(r)) 以下の回数の比較・交換をおこない， a[i] から a[r] までをヒープにできる。
(9.1.7) 証明：次の例で考えよう。 a[4] から a[31] までがヒープになっている。 これを，a[3] から a[31] までがヒープになっているように変えたい。
35
82 37
97 67 96 95
96 95 49 37 76 92 94 58
57 21 81 19 06 22 23 26 72 18 26 32 46 57 02 18
いま考えている範囲より上の a[1] と a[2] は関係してこないし， 左半分もこれからの操作で変わらないので，「--」で置き換える。
--
-- 37
-- -- 96 95
-- -- -- -- 76 92 94 58
-- -- -- -- -- -- -- -- 72 18 26 32 46 57 02 18
ヒープの条件を満たしていないのは， a[3] である 37 とその子との間のみである。 それ以外をいったん「--」に置き換えてみる。
--
-- 37
-- -- 96 95
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
ここで，「この三つの元のうちの二つに互換をほどこし， この三つの元の間では親が子以上となるようにせよ」と言われたら， 三つの元のうちで一番大きい 96 を親の 37 と入れ替えることになる。
--
-- 96
-- -- 37 95
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
こうなった。「--」で置き換えてあった部分を戻そう。
--
-- 96
-- -- 37 95
-- -- -- -- 76 92 94 58
-- -- -- -- -- -- -- -- 72 18 26 32 46 57 02 18
こんどは，一段下にさがった 37 とその子の間で大小関係が合わなくなった。 合わないのはそこだけである。
--
-- --
-- -- 37 --
-- -- -- -- 76 92 -- --
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
だから，この三つの間でまた同じことをする。 すなわち，一番大きい 92 を親の 37 と入れ替える。
--
-- --
-- -- 92 --
-- -- -- -- 76 37 -- --
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
「--」で置き換えてあった部分を戻すと次のようになる。
--
-- 96
-- -- 92 95
-- -- -- -- 76 37 94 58
-- -- -- -- -- -- -- -- 72 18 26 32 46 57 02 18
こんどは，37 とその子の間で大小関係が合っている。 これで操作は完了である。 いまおこなった比較や交換の回数は上の図の高さ， すなわち log(r) の何倍かで押さえられる。
(9.1.8) ※ ここで，上にあがった 92 がその上の 96 と親子の関係になったが， その間の大小関係は大丈夫だろうか，と気になるかもしれない。 が， それはもともと親子関係にあったものが一段ずつ上にあがってまた親子になっただけなので大丈夫なのである。
(9.1.9) ※ 上の操作を，別の言いかたで説明しよう。 a[3] だった 37 から下へ進む。 一般に子は二つあるが，より大きな子のほうへと進んでゆく。 すると，次のような曲がった道ができる。
--
-- 37
-- -- 96 --
-- -- -- -- -- 92 -- --
-- -- -- -- -- -- -- -- -- -- -- 32 -- -- -- --
仮定により，この列の中では数値は下へゆくほど小さくなり，上へゆくほど大きくなる。 ここに，挿入ソートと似た操作をおこなうと，次のようになる。
--
-- 96
-- -- 92 --
-- -- -- -- -- 37 -- --
-- -- -- -- -- -- -- -- -- -- -- 32 -- -- -- --
これが上でおこなった操作である。 位置が変わる要素はここで示した道の上にあるものだけであり， しかもそれは一つ上にあがるだけである。 ここで少し考えると， 操作後は a[3] 以降がヒープになっていることがわかる。
(9.1.10) 上の操作を関数にしたものを void downheap(int i, int r) としよう。 ヒープソートの原理は次のとおりである。
第一段は明らかであろう。
第二段を説明する。 配列全体，すなわち a[1] から a[N] までがヒープになっていれば， この中で最大の元（の一つ）は a[1] である。 だから，それを a[N] と交換すれば a[N] は確定する。 そして，a[2] から a[N-1] までは依然としてヒープである。 よって，次には a[N] はもう見ないことにして， 関数 downheap() を利用し a[1] から a[N-1] までをヒープに再構築する。 このヒープの中で最大の元（の一つ）は a[1] であるから， それを a[N-1] と交換すれば a[N-1] は確定する。 これのくり返しである。
(9.1.11) 第一段も第二段も， 一つの元を処理するのにかかる手間は Ο(log(N)) 以下であるから， 全体で Ο(N log(N)) 以下の計算量となる。 オーダーがこれより小さくはならないことは前に見たので， ヒープソートの計算量は Ο(N log(N)) である。 これは Ο(N2) だったいままでのソートよりもすぐれたアルゴリズムである。
(9.2.1) 課題１と同様のことを，ヒープソートについておこなえ。
(9.2.2) 挿入ソートのプログラムをコピーしたものから始めよう。 ファイル名は heap.c でよいだろう。 関数 print() を次で置き換える。 これは，N の値が 16 以上 31 以下のとき， 配列に代入されている値を上の (9.1.7) のようなスタイルで出力するものである。 （スペースの数を調整してあるので， コピー & ペーストすることを *強く* すすめる。）
void print(void) {
int i;
printf(" %02d\n", a[1]);
printf(" %02d %02d\n", a[2], a[3]);
for (i = 4; i <= 7; i++) {
printf(" %02d ", a[i]);
}
printf("\n");
for (i = 8; i <= 15; i++) {
printf(" %02d ", a[i]);
}
printf("\n");
for (i = 16; i <= N; i++) {
printf("%02d ", a[i]);
}
printf("\n");
}
(9.2.3) 関数 downheap() では， まず，a[i] とその左右の子（もしあれば）とを比較する。 親が最大だったらそれでおしまい。 子のほうが大きかったら，左右のうちで大きいほうと親とを入れ換え， 次は注目箇所をその子に移動する。 すなわち，i を変更する。 これのくり返しである。 よって，全体は次のような感じになるだろう。
（この関数の中での関数 comp() の呼び出しは四回で済む。 すぐに思いつかない人は， 五回以上になってもよいから正しく動くものを書いてみて， あとで減らすことを考えよう。）
void downheap(int i, int r) {
for (ここは空白; ... <= r; ここも空白) { /* この範囲内に子がある限り */
if (... <= r) { /* 左右に子がいるとき */
if (...) { /* 親が最大のとき */
return; /* このときはヒープ化完了 */
} else if (...) { /* 左の子が最大のとき */
swap(i, 2*i); /* 親と左の子を交換 */
i = 2*i; /* 注目箇所を左の子に移動 */
} else { /* 右の子が最大のとき */
...
...
}
} else { /* 左の子のみのとき */
if (...) { /* 親が大きいとき */
return; /* このときはヒープ化完了 */
} else { /* 左の子が大きいとき */
swap(i, 2*i);
return; /* なぜこれでよいのか，考えよ */
}
}
}
}
swap() の中から print() を呼べば， 正しく動いているかどうか確認できる。
(9.2.4) 今回は，main() は比較的容易である。 まずは，main() は (9.1.10) の第一段のみとし， 関数 downheap() が正しく書けたかどうかのチェックをおこなう。 途中経過のメッセージも出すとよい。 「a[3](=78) から最後までをヒープにします」 「ヒープ化完了」など。
(9.2.5) 第一段は downheap(i, N) を実行するが，このとき， 第二の引数は N で，一定である。 N が偶数の場合と奇数の場合の両方で，downheap() が正しく書けているかどうかチェックする必要がある。 第一段で左の子しかいない場合が発生するための条件は N が偶数であることだから。
(9.2.6) 第一段が正しく書けたと確信できたら，第二段を追加する。 （今回は，for ループが二つ並ぶことになる。 二重ループではない。）
(9.2.7) 第二段の途中メッセージは 「a[9](=78) は確定しました. a[1] から a[8] までをヒープに再構築します」 など。各自で工夫せよ。 （注意：「再構築」と出力させるには， ソースファイルには「再構\築」と書くこと。 これはコンパイラの都合である。）
(9.2.8) 件名は「?? kadai3」（「??」は自分のアカウント名の下二桁。 全て半角文字，アルファベットは小文字。 kadai と 3 の間にはスペースをいれない）とせよ。 これ以外の注意点は課題１と同じ。
(9.2.9) N の値を大きくしての実験は， N を 10000, 100000, 1000000 にして，五回ずつおこなえ。
(9.2.10) N の値を大きくして実験をするようになったら， 関数 print() は使えなくなってしまうが， レポートにはそのまま残しておくこと。
(9.3.1) N を 1000000 にした場合，220 = 1048576 だから， ヒープの高さは約 20 である。意外と小さい。 「曽呂利新左衛門と米粒の話」の“あべこべ”，とでもいえようか。 ここが，このソートの“みそ”である。
(9.3.2) 地球の人口は 70 億人を超えているらしい。 233 = 8589934592 なので， 全人類が，一人が二人に伝達する緊急連絡網を作ると， それは約 33 段で済む。