   
（１）ヒープ
ヒープ（heap）とは，「累積」，「積み重なったもの」
という意味ですが，
ここでは，親の値が子供の値以上であるような完全２分木を
意味します。
たとえば，次のような木をヒープといいます。
ただし，２分探索木と異なり，
必ずしも左のノードが右のノードより小さいとは限りません。
（２）完全２分木の配列による表現
完全２分木を次のように配列で表現します。
■ルートをＡ［0］に入れる。
■その直接の左の子をＡ［１］に，右の子をＡ［２］に入れる。
■更に１つ下流に下って左から格納する
このように配置すると，親子の位置関係は，次のようになります。
■Ａ［Ｉ］の親は，Ａ［（Ｉ−１）／２］
■Ａ［Ｉ］の左の子は，Ａ［Ｉ＊２＋１］
■Ａ［Ｉ］の右の子は，Ａ［Ｉ＊２＋２］
例えば，次のように配置します。
（３）ヒープソート
ヒープを利用することで，以下の手順でソートすることができます。
@）ヒープのルートから値を取り出すと最大値が得られる。
A）ヒープの最後の要素を先頭に移し，ヒープを再構築する。
B）最大値を配列の最後に入れる。
ヒープの再構築は次のように行います。
@）根を取り出し，そこにヒープ最後の要素を移動
。
A） ２つの子を比較し，大きい方の子と交換する・
B） リーフに届く,または左右の子が自分より小さくなるまで
A）を繰り返す。
（４）ヒープの構築
ヒープを構築するには，下流側の部分木からボトムアップ的に積み上げます。
最後の処理は，ヒープの再構築の処理とほぼ同じになります。
この意味で，ヒープ全体の構築は，
下流側の部分木から再構築する処理を行えばよいことが分かります。
［プログラム］
private void ヒープ化(ref int[] a, int
左, int 右)
{
int AA = a[左]; int 子; int
親;
for(親 = 左; 親 < (右 + 1)/2 ;
親 = 子)
{
int 左の子 = 親 * 2 + 1; int
右の子 = 左の子 + 1;
子 = (右の子 <= 右 &&
a[右の子]>a[左の子]) ? 右の子 : 左の子;
if(AA >= a[子]) break;
a[親]=a[子];
}
a[親]=AA;
}
private void ヒープソート()
{
int i;
for (i = (Data.Length - 1) / 2;i
>= 0; i--)
ヒープ化(ref Data, i, Data.Length
- 1);
for (i = Data.Length - 1 ;i >
0; i--)
{
swap(ref Data[0], ref
Data[i]);
ヒープ化(ref Data, 0, i-1);
}
}
 1. 基本的なアルゴリズム
2. 基本的なデータ構造
3. 操作を伴うデータ構造
4. 探索
5. 再帰的アルゴリズム
6. ソート
7. 集合
8. 文字列処理
9. 色々なアルゴリズム
上のタイトルをクリックします
|
6．8 ヒープソート