ヒープソートとは
ここではソートのアルゴリズムの一つであるヒープソートを学習します。
ヒープソートとはヒープ木を作ることで列内の最大もしくは最小値を見つけ出し、それを除いた残りの値で同様の作業を繰り返すことで並べ替えを行う方法です。
これだけではよくわからないでしょうから詳しく解説していきます。
まずはヒープ木とは何かについてです。
ヒープ木とは木構造の一つで
①完全二分木で、
②親が子よりも大きく(小さく)なるように並べられた木のことです。
完全二分木とは一つの親ノードに対して子ノードが2つ以下である木構造のことです。
上の図でいうと[1]は[3]と[4]よりも大きい値となります。同じ階層の要素の順番はばらばらでも問題ありません。
つまり、ヒープ木として並べた場合、[0]が最大の値となります。
このヒープ木を使ってソートを行うのがヒープソートです。
ヒープ木は最大値を求めることが出来るのでヒープ木を並べることで一つだけ値の順番を特定できます。
そして残りの中で再びヒープ木を作れば2番目に大きい値を求められます。
これを繰り返すことですべての値を順番に並べます。
具体的に言うと、二回目は[0]と[6]の値を入れ替えて、[0]から[5]までのヒープ木を作ります。
以下の配列を例に見ていきましょう。
| 添え字 | [0] | [1] | [2] | [3] | [4] | [5] | [6] |
| 値 | 7 | 2 | 6 | 9 | 0 | 5 | 8 |
このなかでヒープ木を作ります。
| 添え字 | [0] | [1] | [2] | [3] | [4] | [5] | [6] |
| 値 | 7 | 9 | 8 | 2 | 0 | 5 | 6 |
[0]は[1]と[2]より大きいのでそのままです。
[1]を[3]と[4]と比べると[3]が一番大きいので並べ替えます。
[2]を[5]と[6]と比べると[6]が一番大きいので並べ替えます。
| 添え字 | [0] | [1] | [2] | [3] | [4] | [5] | [6] |
| 値 | 9 | 7 | 8 | 2 | 0 | 5 | 6 |
[0]を[1]と[2]と比べると[1]が一番大きいので並べ替えます。
これで[0]に一番大きい値が来ました。
| 添え字 | [0] | [1] | [2] | [3] | [4] | [5] | [6] |
| 値 | 6 | 7 | 8 | 2 | 0 | 5 | 9 |
以下同様に[0]から[5]までで並び替えていきます。
ソースコード
以下がソースコードです。
heapsort_sample1.c++
#include <stdio.h>
#define A_LEN 10
void show(int a[])
{
for (int i = 0; i < 10; i++)
printf("%d ", a[i]);
printf("\n");
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void heapsort(int a[], int a_len)
{
int childL, parent;
while (a_len > 0)
{
printf("a_len = %d\n", a_len);
parent = a_len - 1;
while (parent >= 0)
{
childL = parent * 2 + 1; //parentの左の子の添え字
if (childL < a_len)
{
if (a[childL] < a[childL + 1] && childL + 1 < a_len) //左右で大きいほうを左の子にする
swap(&a[childL], &a[childL + 1]);
if (a[childL] > a[parent]) //子が親より大きければ入れ替え
swap(&a[childL], &a[parent]);
}
show(a);
parent--;
}
swap(&a[0], &a[a_len - 1]);
show(a);
a_len--;
}
return 0;
}
int main(void)
{
int a[A_LEN] = { 7, 9, 6, 8, 0, 1, 5, 10, 3, 2 };
int a_len = A_LEN;
show(a);
heapsort(a, a_len);
show(a);
return 0;
}