(41.1) ヒープソートに登場する「ヒープ (heap)」は 「木」と呼ばれるデータ型の一種である。 一般の木を扱う方法はこの授業では取りあげない。 また、ヒープという言葉はコンピュータの世界ではこれ以外にもいろいろな意味で使われる。
(41.2) ここでは、 配列 a[1], ..., a[N] において、 「a[2*i] と a[2*i+1] は a[i] の子」 と考える。
(41.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 の値によっては、
この山から右下の一部が欠けたものになる。
(41.4) 上の例の“高さ”が 3 であるか 4 であるかは定義のしかたの問題だが、 いずれにせよ、ほぼ log(N) である。
(41.5) 「a[i] から a[j] までがヒープである」 とは、 a[i], a[i+1], ..., a[j] のうちで親子関係にある全てのペアについて、親が子以上であることをいう。
(41.6) 補題： a[i+1] から a[r] までがヒープになっているとき、 a[i] から a[r] までの要素の間で Ο(log(r)) 以下の回数の比較・交換を行ない、 a[i] から a[r] までをヒープにできる。
(41.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) の何倍かで押さえられる。
(41.8) ※ ここで、上にあがった 92 がその上の 96 と親子の関係になったが、 その間の大小関係は大丈夫だろうか、と気になるかもしれない。 が、 それはもともと親子関係にあったものが一段ずつ上にあがってまた親子になっただけなので大丈夫なのである。
(41.9) ※ 上で行なった操作を、別の言いかたで説明しよう。 a[3] だった 37 から下へ進む。 一般に子は二つあるが、より大きな子のほうへと進んでゆく。 すると、次のような曲がった道ができる。
--
-- 37
-- -- 96 --
-- -- -- -- -- 92 -- --
-- -- -- -- -- -- -- -- -- -- -- 32 -- -- -- --
仮定により、この列の中では数値は下へゆくほど小さくなり、上へゆくほど大きくなる。
ここに、挿入ソートと似た操作を行なうと、
--
-- 96
-- -- 92 --
-- -- -- -- -- 37 -- --
-- -- -- -- -- -- -- -- -- -- -- 32 -- -- -- --
となる。これが上で行なった操作である。
位置を変える要素はここで示した道の上にあるものだけであり、
しかもそれは一つ上にあがるだけである。
ここで少し考えると、
操作後は a[3] 以降がヒープになっていることがわかる。
(41.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] までをヒープに再構築する。 これのくり返しである。
(41.11) 第一段も第二段も、 一つの元を処理するのにかかる手間は Ο(log(N)) 以下であるから、 全体で Ο(N log(N)) 以下の計算量となる。 オーダーがこれより小さくはならないことは前のセクションで見たので、 ヒープソートの計算量は Ο(N log(N)) である。 これは Ο(N2) だったいままでのソートよりもすぐれたアルゴリズムである。
(42.1) 課題１と同様のことを、ヒープソートについて行なえ。
(42.2) まず、GNOME 端末の「編集」「現在のプロファイル...」「スクロール」をクリック。 そして、「スクロールバックのサイズ」を 1000 行に増やしておこう。 こうしておけば、配列の大きさ N を 31 にして実験しても大丈夫である。
(42.3) 挿入ソートのプログラムをコピーしたものから始めよう。 ファイル名は heap.c でよいだろう。 関数 print() を次で置き換える。
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");
}
これは、N の値が 16 以上 31 以下のとき、
配列に代入されている値を上の (41.7) のようなスタイルで出力するものである。
(42.4) 関数 downheap() では、 まず、a[i] とその左右の子（もしあれば）とを比較する。 親が最大だったらそれでおしまい。 子のほうが大きかったら、左右のうちで大きいほうと親とを入れ換え、 次は注目箇所をその子に移動する。 すなわち、i を変更する。 これのくり返しである。 よって、全体は次のような感じになるだろう。
void downheap(int i, int r) {
for (ここは空白; ... <= r; ここも空白) { /* この範囲内に子がある限り */
if (左右に子がいる) {
if (親が最大) {
return; /* このときはヒープ化完了 */
} else if (左の子が最大) {
swap(i, 2*i); /* 親と左の子を交換 */
i = 2*i; /* 注目箇所を左の子に移動 */
} else { /* 右の子が最大のとき */
...
...
}
} else { /* 左の子のみのとき */
if (親が大きい) {
return; /* このときはヒープ化完了 */
} else { /* 左の子が大きいとき */
...
}
}
}
}
(42.5) 今回は、main() は比較的容易である。 まずは、main() は (41.10) の第一段のみとし、 関数 downheap() が正しく書けたかどうかのチェックを行なう。 正しく書けたと確信できたら、第二段を追加する。 （今回は、for ループが二つ並ぶことになる。 二重ループではない。）
(42.6) 途中経過のメッセージも出すとよい。 第一段については 「a[3] から a[31] までをヒープにします」 「完了」、 第二段については 「a[9] は確定しました. a[1] から a[8] までをヒープに再構築します」 「再構築完了」など。
(42.7) 件名は「kadai3」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）とせよ。 これ以外の注意点は課題１と同じである。
(42.8) N の値を大きくしての実験は、 N を 10000, 100000, 1000000 にして、五回ずつ行なえ。
(42.9) N の値を大きくして実験をするようになったら、 関数 print() は使えなくなってしまうが、 レポートにはそのまま残しておくこと。