ヒープソートに登場する「ヒープ」は 「木」と呼ばれるデータ型の一種である。 一般の木を扱う方法はこの授業では取りあげないが、 ヒープは、配列 a[0], ..., a[N-1] において 「a[i] の子は a[2*i+1] と a[2*i+2]」 とみなすことで実現できる。 これの“高さ”は（ほぼ）log(N) である。 言葉の濫用だが、ヒープが 「ヒープになっている」「ヒープである」とは、 条件「親子関係にある任意の二元に対し、親が子以上である」 を満たしていることをいう。
ヒープソートの原理は次のとおり。
第１段も第２段も、 一つの元を処理するのにかかる手間が log(N) 以下であるから、 全体で Ο(N log(N)) 以下の計算量となる。 一般論で、 いかなるソートの計算量もこれより小さくはならないことが知られているので、 ヒープソートの計算量は Ο(N log(N)) である。
a[i] の子以下はヒープになっているとの仮定のもとで a[i] 以下 a[r-1] までをヒープにする関数 void downheap(int i, int r) を書け。
まず、a[i] とその左右の子（もしあれば）とを比較する。 親が最大だったらそれでおしまい。 子のほうが大きかったら、左右のうちで大きいほうと親とを入れ換え、 次は注目箇所をその子に移動する。 すなわち、i を変更する。 これのくり返しである。 よって、
void downheap(int i, int r) {
while (... < r) { /* この範囲内に子がある限り */
if (...) {
return;
} else if (...) {
swap(..., ...);
i = (i の式); /* 注目箇所を子に移動 */
} else ...
...
}
}
}
のような感じになる（かもしれない）。
main() では上で説明した「第１段」のみを行なうようにし、 全体がヒープになることをチェックする。 それには、 i がまん中あたりから始めて 0 まで、1 ずつ減らしながら、 downheap(i, N) を呼び出せばよい。
課題 6-1) ヒープソートのプログラムを書き、課題 4-1 と同じようなことを調べよ。
（上の演習問題が済んでいれば、実は簡単である。）
課題 6-2) 課題 4-2 と同様のことを、ヒープソートについて調べよ。
課題 6-3) 比較の回数も数えてみよ。 （比較は数箇所に出てくるので、ちょっとめんどうである。）
以上から適当に選んで、メールでレポートしてください。
プログラムも送ってください。 その際、Active!Mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。
所要時間を計るにせよ回数を数えるにせよ、 数回くり返して測定し、それらのデータそのものおよび平均値をレポートに書くこと。 それから、理論上の値などと比較すること。 感想は書かなくてもよい。
宛て先は私（岩瀬）の実習用アカウント cf5326@mailedu1.ipc.kanazawa-u.ac.jp です。 件名は「kadai6」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）としてください。 自分の学籍番号、氏名（として大学に届けてあるもの） をメールの *本文内にも* 書くのを忘れずに。
この授業の課題では、 プログラムの完成後、 print() を消し、 N の値を書き換えて何度も実験を行なう。 これらを、 ソースファイルを書き換えずに行なう方法を、 ホームページに書いておいた。 プリントにはしないが、興味のあるものは読んでほしい。 プログラム例などから一部抜き書きしておく。
#define JAPANESE
#ifdef JAPANESE
printf("今日は, 世界\n"); /* ここはコンパイルされる */
#else
printf("hello, world\n"); /* ここは無視される */
#endif
「gcc kadai6.c」の代わりに 「gcc -DDEBUG kadai6.c」としてコンパイルすると、 ソースファイル中に「#define DEBUG」と書いたのと同じ効果。
「gcc -DN=1000 kadai6.c」としてコンパイルすると、 ソースファイル中に「#define N 1000」に書いたのと同じ効果。
これらのオプションをつけてコンパイルするプログラムは、 冒頭にそのことをコメントとして書いておくべきである。 そうでないと、 あとで忘れてしまった場合にコンパイルできなくなる可能性がある。