整列 ―ヒープソート―
ヒープソートとは
ヒープソートは，二分木を用いた整列方法です．
二分木のうち，全ての親ノードと子ノードの間に 親 ≧ 子 の関係，または，全ての親ノードと子ノードの間に 親 ≦ 子 の関係があり，各ノードから可能な限り２つのノードが出ているもの（当然，最下層のノードに子ノードはありませんし，ノードの総数によっては子ノードが１つだけである場合もあります）を ヒープ と呼びます．
お分かりになるように，親 ≦ 子 の関係のあるヒープであれば，最上位の親ノードには全ノードの最小値が入っていることになります．
このことを利用して，整列を行うのがヒープソートです．
それでは，例によって
a[] = {32, 12, 24, 8, 17}
を二分木の上から順に埋めましょう．
データが埋まったら，この二分木を下の方からデータを入れ替えてヒープに作り変えていきます．
下の図の赤で書いた部分が最下層ですから，ここから考えます．
勿論，最下層のノードの組が複数あれば，順に考えます．
赤字の 8 の親ノードには 12 が入っています．
ここを入れ替えます．
赤字の 8 の親ノードには 12 が入っています．
ここを入れ替えます．
入れ替えたら，一層上に上がります．ダンジョンを一階層攻略したら，次の階層に進むとう感じww．
ここでも赤字の 8 の親ノードが 32 ですから，これらを入れ替えます．
ところが，これではまだヒープになっていません．8 と 32 を入れ替えましたからね．
今度は，上から順に，入れ替えた部分を確認していきます．
ここで，32 と 12 とを入れ替えれば，ヒープが出来上がります．当然，最上位ノードの 8 が全ノードの中の最小値です．
そこで，例えば b という配列を作って，b[0] = 8 とします．さらに，最下層にある 17 を最上位に移動して，これを上から順に入れ替えてヒープにしていきます．
17 と 12 を入れ替えればお終いですね．最上位部分以外は 親 ≦ 子 が成り立っているので，入れ替えるべきところまで入れ替えれば作業終了となります．
b[1] = 12 として，後は同じ処理の繰り返しです．
Coding
それでは，例によって10個のデータで並べ替えをしましょう．
#include <stdio.h>
int main(void) {
int a[] = {100, 53, 19, 8, 81, 37, 16, 25, 44, 22};
int len = sizeof(a) / sizeof(int);
int b[len];
int targ;
int i = len;
if (i % 2) {
if (a[i] < a[(i - 1) / 2]) {
int ref = a[(i - 1) / 2];
a[(i - 1) / 2] = a[i];
a[i] = ref;
i--;
}
}
while (i > 0) {
(a[i] < a[i - 1]) ? (targ = i) : (targ = i - 1);
if (a[targ] < a[(i - 1) / 2]) {
int ref = a[(i - 1) / 2];
a[(i - 1) / 2] = a[targ];
a[targ] = ref;
}
i -= 2;
}
for (i = 1; i < len / 2; i++) {
(a[2 * i + 1] < a[2 * i + 2]) ? (targ = 2 * i + 1) : (targ =2 * i + 2);
if (a[targ] < a[i]) {
int ref = a[i];
a[i] = a[targ];
a[targ] = ref;
}
}
if (2 * i + 1 == len - 2 && a[i] > a[2 * i + 1]) {
int ref = a[i];
a[i] = a[2 * i + 1];
a[2 * i + 1] = ref;
}
b[0] = a[0];
for (i = 1; i < len; i++) {
a[0] = a[len - i];
int j = 0;
while ((2 * j + 1 == len - i - 1 && a[j] > a[2 * j + 1]) || (2 * j + 2 < len - i && (a[j] > a[2 * j + 1] || a[j] > a[2 * j + 2]))) {
if (2 * j + 1 == len - i - 1) {
int ref = a[j];
a[j] = a[2 * j + 1];
a[2 * j + 1] = ref;
j = 2 * j + 1;
} else if (a[2 * j + 1] < a[2 * j + 2]) {
int ref = a[j];
a[j] = a[2 * j + 1];
a[2 * j + 1] = ref;
j = 2 * j + 1;
} else {
int ref = a[j];
a[j] = a[2 * j + 2];
a[2 * j + 2] = ref;
j = 2 * j + 2;
}
}
b[i] = a[0];
}
for (i = 0; i < len; i++) {
printf("%d, ", b[i]);
}
printf("\n");
return 0;
}
少々長く，美しさの欠片もないプログラムになってしまいました
長くなっている理由は，完全二分木でないため，子ノードにより場合分けをする必要があったからです．ダミーデータを加えて完全二分木にして処理をするという手もありそうです．また，このような繰り返し処理は，リカージョンを使うこともできそうな気がします．
とか何とも申しても，この程度のコーディングで頭が沸いてしまい，これ以上の思考を拒否しておりまして・・・．まぁ，歳はとりたくないものであります．
そうそう，ご覧になられた方の中には，敢えてヒープにしなくても最上位に最小値がくるのであれば，それを繰り返して整列できるのではないかとお考えになった向きもいらっしゃのでは？ 正にその通りです．ところが，それでは演算の回数が増えて効率が悪くなります．ヒープソートの利点は，例えばバブルソートなどと比較した場合に高速であるということです．この辺りにきますと，アルゴリズムの良さが実感できます．