ソート（並び替え）のアルゴリズムのリビューとして始めたこのシリーズ、バブルソートに続く第2弾です。
今回取り上げるのは「ヒープソート（Heap Sort）」と呼ばれるものです。(今回も詳しく調べられる方の為にwikiの参照を載せます。）
何故"Heap（「積み重ね、かたまり、山」）"と言い始めたのかは分かりませんが、以下のように二分木を使った並び替え方法（アルゴリズム）です。
//////////////
// Heap Sort
//////////////
/*
ヒープソートは次のようなヒープ（二分木）の「親－子」関係を用いる
Parent(0)
／＼
ChildL(1) ChildR(2)
この二分木を用いて配列を表現すると以下のようになる（数字は添字）
0
／ ＼
1 2
／ ＼ ／ ＼
3 4 5 6
／ ＼
7 8 ...
*/
//////////////////////////////////////////////////////////
//解説：ヒープソートのから呼び出されるサブ関数
//////////////////////////////////////////////////////////
void exchange(int top, int* data, int n) {
int temp = data[top]; //開始時の二分木の親の値をtempに退避
//子のある二分木の左の子供を指定し、（交換があればやり直す為）末尾迄子孫を辿る
for(int i = top * 2 + 1; i < n; top = i, i = top * 2 + 1) {
if(i < n - 1 && data[i] < data[i + 1]) //右の子供が左の子供より大きければ
i++; //右の子供を指定する
if(temp >= data[i]) //開始時の親と大きい方の子供を比較
break; //親が大きければループを抜ける（topは変化しない）
data[top] = data[i]; //二分木の親に大きい子の値を代入する
} //大きい子（data[i]）はループのi = topで
data[top] = temp; //data[top]となり、退避した親の値を代入
}
//////////////////////////////////////////////
//解説：これがヒープソート本体の関数
//////////////////////////////////////////////
void heapsort(int* data, int n) {
int top, i;
for(top = n / 2 - 1; top >= 0; top--) //最初に「子がある最後の二分木」から
exchange(top, data, n); //「親が最大値を持つ」ように頂点まで継続する
for(i = n - 1; i > 0; i--) { //次に配列の最後と頂点（最大値）の値を交換し
int temp;
temp = data[i];
data[i] = data[0];
data[0] = temp;
exchange(0, data, i); //解説：ヒープソートのから呼び出すサブ関数
} //配列の最後を切り離し、その前の要素から頂点まで継続する
}
これだけではどのように並び替えが行われるのかよく分かりませんよね？
ヒープソートは直観的に理解するのが少し難しいので、今回も具体的に
配列 = {2, 7, 3, 5, 4, 0, 6, 1, 8};
要素数 9
を想定して実際の処理につき、変更された値は橙、最大値は赤で以下に解説します。
１．原型
2 解説：data[0]
／ ＼
7 3 解説：data[1]とdata[2]
／ ＼ ／ ＼
5 4 0 6 解説：data[3] ～ data[6]
／ ＼
1 8 ... 解説：data[7]からdata[8]
配列 = {2, 7, 3, 5, 4, 0, 6, 1, 8};
２．HeapSortの第1ループとexchange
(1) top == 3 解説：forループの初期化がtop = n / 2 - 1なので。（これは子のある最後の二分木を指す。）
2
／ ＼
7 3
／ ＼ ／ ＼
5 4 0 6 解説：このdata[3]（5）が
／ ＼
1 8 ... 解説：data[8]（8）（> data[7]（1））と比較され、交換される
解説：世代の最後である第3世代から始めますが、8 > 1なので、（top * 2 + 1で7であった）iはインクリメント（i++;）され8となる為、親の5と右の子8の比較となり、交換が生じます。交換は
data[top] = data[i]; //二分木の親に大きい子の値を代入する
と、forループの事後処理の
top = i, i = top * 2 + 1
により、元の親の値（temp（5））がdata[top]、即ち元のi（8）に代入される
data[top] = temp;
ことで成立します。又この段階で新しいiが17（8 * 2 + 1）となり、forループを抜けます。
配列 = {2, 7, 3, 8, 4, 0, 6, 1, 5};
(2) top == 2 解説：forループの事後処理がtop--なので。
2
／ ＼
7 3 解説：この3が
／ ＼ ／ ＼
8 4 0 6 解説：この6（> 0）と比較され、交換される
／ ＼
1 5 ...
解説：同様にtopが2となり、親が3、子が0と6の二分木を処理します。右の子（6）が左の子（0）より大きいので、親の3と右の子（6）が比較され、交換されます。ここでもiは事後処理で13となり、ループを抜けます。
配列 = {2, 7, 6, 8, 4, 0, 3, 1, 5};
(3) top == 1 解説：forループの事後処理がtop--なので。
2
／ ＼
7 6 解説：この7が
／ ＼ ／ ＼
8 4 0 3 解説：この8と比較され、交換される
／ ＼
1 5 ...
解説：同様にtopが1となり、親が7、子が8と4の二分木で、親の7と左の子（8）が比較され、交換されます。ここではiが事後処理で7となり、親が8、子が1と5の二分木についても比較が行われ、親が大きいので（break;）交換は行われません。
配列 = {2, 8, 6, 7, 4, 0, 3, 1, 5};
(4) top == 0 解説：forループの事後処理がtop--なので。（条件式：top >= 0）
2 解説：この（tempに保存される）2が
／ ＼
8 6 解説：この8と比較され、親（2）に8が代入される
／ ＼ ／ ＼
7 4 0 3
／ ＼
1 5 ...
解説：最後にtopが0、i が1となり、親が2、子が8と6の二分木で、親の2と左の子（8）が比較され2のあった場所（data[0]）に8が代入されます。
8
／ ＼
8 6
／ ＼ ／ ＼
7 4 0 3
／ ＼
1 5 ...
解説：ここでも事後処理
top = i, i = top * 2 + 1
でtopにi（1）が代入され、iが3（top * 2 + 1）となり、親が8、子が7と4の二分木についても「最初の親の値（temp（2））」と比較が行われ、data[3]の7が大きいので交換は行われます。
8
／ ＼
7 6
／ ＼ ／ ＼
7 4 0 3
／ ＼
1 5 ...
解説：更に事後処理
top = i, i = top * 2 + 1
でtopにi（3）が代入され、iが7（top * 2 + 1）となり、親が7、子が1と5の二分木についても「最初の親の値（temp - 2）」と比較が行われ、左の子より右の子が大きいのでiはインクリメントされて8となり、data[8]の5が大きいので交換7のあったdata[[3]に5が代入され、
8
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／ ＼
1 5 ...
解説：iが17（top * 2 + 1）となったのでループを抜けて、5があったdata[8]に2が代入されて交換が完了します。
8
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／ ＼
1 2 ...
解説：最終的に次のような配列となります。
配列 = {8, 7, 6, 5, 4, 0, 3, 1, 2};
３．HeapSortの第2ループとexchange
解説：HeapSortの第1ループのtopの値が"top--;"により-1になったので、第1ループを抜けます。第2ループでは最大値を最後尾にと交換し、最大値の8を除外し、要素数を1減らされた8にして二分木の頂点から下に向かって同じ処理を繰り返し（for(i = n - 1; i > 0; i--)、exchange(0, data, i);）行います。
2
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／ ＼
1 8 ...
解説：先ずは最大値8を除外して要素数iが8の配列の変化を示します。
2
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／
1 ...
7
／ ＼
7 6
／ ＼ ／ ＼
5 4 0 3
／
1 ...
7
／ ＼
5 6
／ ＼ ／ ＼
5 4 0 3
／
1 ...
7
／ ＼
5 6
／ ＼ ／ ＼
2 4 0 3
／
1 ...
配列 = {7, 5, 6, 2, 4, 0, 3, 1, 8};
解説：次に最大値7を除外した新しい二分木を要素数7で同様の処理を続けます。
5
／ ＼
6 2
／ ＼ ／ ＼
4 0 3 1...
| |
＼ ／
配列 = {5, 6, 2, 4, 0, 3, 1, 7, 8};
6
／ ＼
5 3
／ ＼ ／ ＼
2 4 0 1...
| |
＼ ／
配列 = {5, 3, 2, 4, 0, 1, 6, 7, 8};
解説：更に最大値6を除外した新しい二分木を要素数6で同様の処理を続けます。
5
／ ＼
3 2
／ ＼ ／
4 0 1...
| |
＼ ／
配列 = {4, 3, 2, 1, 0, 5, 6, 7, 8};
解説：このようにして同じ処理を繰り返してゆき、末尾から8、7、6、5 ...と第2ループの最大値が並んでゆき、並び替えが完了して最後に配列は次のようになります。
配列 = {0, 1, 2, 3, 4, 5, 6, 7, 8};
如何でしたか？ちょっととっつきにくかったかもしれませんが、wikiの記事と共にご確認ください。
【ご参考】（解説：↑の例のヒープソート実行中のexchange関数における配列変化の出力）
>>> オリジナルデータ <<<
2, 7, 3, 5, 4, 0, 6, 1, 8
>>> Heap Sort <<<
--- top = 3 and i = 8 ---
2, 7, 3, 8, 4, 0, 6, 1, 8
--- top = 8 ---
2, 7, 3, 8, 4, 0, 6, 1, 5
--- top = 2 and i = 6 ---
2, 7, 6, 8, 4, 0, 6, 1, 5
--- top = 6 ---
2, 7, 6, 8, 4, 0, 3, 1, 5
--- top = 1 and i = 3 ---
2, 8, 6, 8, 4, 0, 3, 1, 5
--- top = 3 ---
2, 8, 6, 7, 4, 0, 3, 1, 5
--- top = 0 and i = 1 ---
8, 8, 6, 7, 4, 0, 3, 1, 5
--- top = 1 and i = 3 ---
8, 7, 6, 7, 4, 0, 3, 1, 5
--- top = 3 and i = 8 ---
8, 7, 6, 5, 4, 0, 3, 1, 5
--- top = 8 ---
8, 7, 6, 5, 4, 0, 3, 1, 2
--- top = 0 and i = 1 ---
7, 7, 6, 5, 4, 0, 3, 1, 8
--- top = 1 and i = 3 ---
7, 5, 6, 5, 4, 0, 3, 1, 8
--- top = 3 ---
7, 5, 6, 2, 4, 0, 3, 1, 8
--- top = 0 and i = 2 ---
6, 5, 6, 2, 4, 0, 3, 7, 8
--- top = 2 and i = 6 ---
6, 5, 3, 2, 4, 0, 3, 7, 8
--- top = 6 ---
6, 5, 3, 2, 4, 0, 1, 7, 8
--- top = 0 and i = 1 ---
5, 5, 3, 2, 4, 0, 6, 7, 8
--- top = 1 and i = 4 ---
5, 4, 3, 2, 4, 0, 6, 7, 8
--- top = 4 ---
5, 4, 3, 2, 1, 0, 6, 7, 8
--- top = 0 and i = 1 ---
4, 4, 3, 2, 1, 5, 6, 7, 8
--- top = 1 and i = 3 ---
4, 2, 3, 2, 1, 5, 6, 7, 8
--- top = 3 ---
4, 2, 3, 0, 1, 5, 6, 7, 8
--- top = 0 and i = 2 ---
3, 2, 3, 0, 4, 5, 6, 7, 8
--- top = 2 ---
3, 2, 1, 0, 4, 5, 6, 7, 8
--- top = 0 and i = 1 ---
2, 2, 1, 3, 4, 5, 6, 7, 8
--- top = 1 ---
2, 0, 1, 3, 4, 5, 6, 7, 8
--- top = 0 ---
1, 0, 2, 3, 4, 5, 6, 7, 8
--- top = 0 ---
0, 1, 2, 3, 4, 5, 6, 7, 8
Push CR key ...