ヒープソートに登場する「ヒープ」は 「木」と呼ばれるデータ型の一種である。 一般の木を扱う方法はこの授業では取りあげないが、 ヒープは、配列 a[0], ..., a[N-1] において 「a[i] の子は a[2*i+1] と a[2*i+2]」 とみなすことで実現できる。 これの“高さ”は（ほぼ）log(N) である。 言葉の濫用だが、ヒープが a[...] から a[...] まで 「ヒープになっている」「ヒープである」とは、 条件「この範囲にあって親子関係にある任意の二元に対し、親が子以上である」 を満たしていることをいう。
ヒープソートの原理は次のとおり。
第１段も第２段も、 一つの元を処理するのにかかる手間が log(N) 以下であるから、 全体で Ο(N log(N)) 以下の計算量となる。 一般論で、 いかなるソートの計算量もこれより小さくはならないことが知られているので、 ヒープソートの計算量は Ο(N log(N)) である。
a[i] の子以下
a[i+1] から a[r-1] まではヒープになっているとの仮定のもとで
a[i] 以下から a[r-1] までをヒープにする関数
void downheap(int i, int r) を書け。
--- 以下、訂正箇所はないので省略 ---