ヒープ(完全2分木)、優先度付きキューを用いた高速な整列アルゴリズム
最大値が木構造の根(ルート)に位置することを利用してソートを行う
ヒープから最大値である根を取り出す作業を繰り返し、その過程で取り出した値を並べることでソートする。
ヒープソートは「選択ソートの応用アルゴリズム」とも見ることができる。
1 》ヒープソート図解
ヒープ上の要素格納- 最も上位に位置する根(ルート)をh[0]に格納
- 1つ下位に降りて要素を左から右へとなぞる
- なぞる過程で添え字を1つ増加、配列の各要素へ格納
- 以上の行程を最下流まで繰り返す
- ヒープの配列への格納を完了
この手順でヒープを配列に格納した時、親の添え字と子の添え字の間で次の関係が成立する。
任意の要素a[i]に対して
- 親:a[(i-1)/2]
- 左の子:a[i*2+1]
- 右の子:a[i*2+2]
具体例を次に示す(昇順)
ソート前の配列ではこのように2分木にそれぞれ値が入っている。
この時、h[2]の子の値(8)がh[0]の親の値(6)より大きいのでh[0]とh[2]の値を入れ替えると
このようになり、それぞれ親の要素が大きく、子の要素が小さいという関係になっている。
この先頭の要素と末尾の要素を入れ替え、h[4]をソート済みとする。
ソート済みの末尾の要素を無視して再びヒープを構築すると以下のようになる
先頭の要素を未ソート部の末尾と入れ替え、ソート済みとする。
以上の操作を繰り返すことで、配列を昇順(小さい順)に並び替える。
特徴
- 同一キーを持つ要素の順序がソート前後で維持されない
- データ出現の順序による計算量の変化が小さい。
- 整列のための特別な作業領域を必要としない
- 平均的にクイックソートより遅い
計算量
データ数をNとすると
データの追加/取り出し操作 O(logN)
ヒープソートのオーダー O(NlogN)
2 》ヒープソートプログラム
配列を昇順に並び替える
【JavaScript】
function heap_sort(numbers,array_size)
{
var temp;
//ヒープ構築
//二分木なので親ノードのインデックス
//(n-1)/2
for(var i=parseInt((array_size-1)/2);i >= 0;i--)
{
max_heap(numbers,i,array_size-1);
}
//ヒープソート実行
//値を昇順に並べる。
//先頭要素(最大値)を配列の最後に移動
//最後の要素を無視してヒープを構築
//配列内で最も小さな値から順に並ぶ
for(var i=array_size-1;i > 0;i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
max_heap(numbers,0,i-1);
}
}
//Max-heap を構築
//親ノードは子ノードより大きいか等しい
//@param numbers ソートしたい配列
//@param root 親ノードとなる要素のインデックス
//@param bottom 最後の要素のインデックス
function max_heap(numbers,root,bottom)
{
//子ノードのインデックス
var child = (2*root)+1;
//親ノードの値を保持
var temp = numbers[root];
while(child <= bottom)
{
if(child < bottom && numbers[child+1] > numbers[child])
{
//二分木のふたつの子ノードから値が大きい子ノードを選択
child = child + 1;
}
if(temp > numbers[child])
{
//親ノードの値が子ノードの値より大きい場合何もしない
break;
}
else if(temp <= numbers[child])
{
//親が子より小さいか等しいとき
//親と子を入れ替える
numbers[parseInt((child-1)/2)] = numbers[child];
//子ノードのインデックスを進める
child = (2*child)+1;
}
}
//親ノードとなる要素に値を入れる
numbers[parseInt((child-1)/2)] = temp;
}
//Max-heap を構築する。再帰を利用。
function max_heap_recursive(numbers,root,bottom)
{
//子ノードのインデックス
//配列の先頭要素のインデックスが 0
//子ノードは 2n+1 と 2n+2 で計算する
var l_idx = (root*2)+1;
var r_idx = (root*2)+2;
//最大値を持つ要素のインデックス
var maxChild;
if(l_idx <= bottom && numbers[l_idx] > numbers[root])
{
maxChild = l_idx;
}
else
{
maxChild = root;
}
if(r_idx <= bottom && numbers[r_idx] > numbers[maxChild])
{
maxChild = r_idx;
}
if(maxChild != root)
{
var temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
//配列の先頭要素には最大値を持つ要素のインデックスを指定
max_heap_recursive(numbers,maxChild,bottom);
}
}
//ここから開始
var h=[6,3,8,4,5,1,2,9,7,0];
document.write("整列前:");
for(var i=0; i < h.length;i++)
{
document.write(h[i]+" ");
}
document.write("<br>");
//ヒープソート
heap_sort(h,h.length);
document.write("整列後:");
for(var i=0; i < h.length;i++)
{
document.write(h[i]+" ");
}
【実行結果】
整列前:6 3 8 4 5 1 2 9 7 0
整列後:0 1 2 3 4 5 6 7 8 9
コメント
このブログにコメントするにはログインが必要です。
さんログアウト
この記事には許可ユーザしかコメントができません。