ヒープソート

ヒープソート
クラス	ソート
データ構造	配列

出典: フリー百科事典『ウィキペディア（Wikipedia）』

移動：案内, 検索

ヒープソート (heap sort) とはリストの並べ替えをヒープ構造を用いて行うソートのアルゴリズムである^[1]。

アルゴリズムは、以下のように2つの段階から構成される。

未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。

計算量は O $(n \log n)$ となる^[1]。安定ソートではない^[1]。

[編集] 実装

ヒープ構造は、ポインタ等の制御用データが不要で、データ自体の配列だけで表現できるという利点がある。ヒープソートを実装する際には、この利点を使い、元データの配列として確保された領域をヒープ構造や整列済みリストに転用していく。

最初にN個のデータを含む配列が与えられるものとする。添字は1 〜 Nとする。

まず各データをヒープ構造に登録していく。m個のデータを処理した状態では、添字1 〜 mがヒープ構造で、(m + 1) 〜 Nが未整列リストとなる。m + 1個目のデータを取り出し、ヒープ構造に登録する。このとき構成するヒープは、昇順にソートする場合はルートが最大値になるよう、降順にソートする場合はルートが最小値になるよう構成すると良い。

すべてのデータをヒープ構造に登録し終えたら、ヒープからの取り出しに移る。ヒープのルートを取り出し、配列の後ろから詰めていく。mを Nから1まで減じながら、取り出したルート要素を配列の添字mに置く。すなわち、(N - m)個のデータを取り出した状態では添字1 〜 mがヒープ構造であり、m + 1 ～ Nが整列済みリストとなる。

すべてのデータをヒープ構造から取り出し終えると、配列全体が整列済みになる。

[編集] 例

ヒープの木構造表現

ヒープソートでは、まずデータの格納されている配列を右の画像のような木構造（2分ヒープ木構造）で表現する（ノード内の数字は配列の添字）。これは、あくまで配列をこのように見なすというだけであり実際に配列を木構造に変化させる訳ではないことに注意する。このとき親を持つノードの番号をnとしたとき子の番号は必ず2nおよび2n + 1である（ヒープ参照、添字を 0からにするときは子の番号は2n + 1と2n + 2になる）。

アルゴリズムの実装の具体例として

data[1 .. 12] := 10 4 8 5 12 2 6 11 3 9 7 1

という数字を昇順にソートする場合を考えてみる。この例を木構造で表すと、

のようになる。この木をヒープの条件を満たすようにする。すなわち全てのノードの子はその親より小さい値になるようにする。これは

ノードが子を持っていないならそのまま。
ノードが一つしか子を持っていないなら子と自分の値を比べて子の方が大きいなら入れ換える。
ノードが二つの子を持つ場合
1. 両者の子以下の木構造をヒープ構造に変換する（再帰呼び出しで行う）。
2. 自分の値と二つの子の値を比べて、最も大きい値が子の場合入れ換える。
3. 入れ換えが起きたなら、入れ換えが起きた方の子以下の木構造をもう一度ヒープ構造に変換する。

という処理を再帰的に行うことでヒープ構造が生成される。dataの例では

という形になる。このとき根の値（ここでは12）がこの配列の最大値である。そこで根と配列としたとき最も端の値（ここでは1が入っている場所）を入れ換えると下のようになる。（12は整列済みになったので木構造から外す。）

今度は木構造の要素の数を 11にして同じ事を繰り返す。すると今度は根に11（残った要素での最大値）が来るのでまた根と端（配列として11番目の場所）を入れ換えてやはり要素の数を1つ減らして同様の処理を繰り返す。これを要素が1になるまで繰り返すと配列の内部は

data[1 .. 12] = 1 2 3 4 5 6 7 8 9 10 11 12

と整列した形になる。

[編集] 擬似コード

擬似コードで表すとヒープソートは以下のようになる。

ヒープ構造へ変換する
procedure make_heap(data[1 .. max], i)
  j := i * 2
  k := i * 2 + 1
  if j > max then
    return
  if j = max then
    if data[j] > data[i] then swap(data[i], data[j])
    return
  end if
  make_heap(data, j)
  make_heap(data, k)
  if data[j] > data[k] then d := j else d := k
  if data[i] < data[d] then
    swap(data[i], data[d])
    make_heap(data, d)
  end if
end

ヒープソート
procedure heap_sort(data[1 .. max])
  while max > 1 do
    make_heap(data, 1)
    swap(data[1], data[max])
    max := max -1
  end while 
end

ここでswap(data[i], data[j])は、data[i]とdata[j]の中身を入れ換えるという関数だが、この関数の実装は省略する。

[編集] 非再帰版ヒープソート(C言語)

ヒープソートは決まった回数のループなので、再帰を用いずに記述することができる。その実装例を以下に示す。なお、nをデータ数、data[]をデータ配列とする。また、swapの実装は上記同様省略する。

 int save,i,j,v;
 
 for(i=n-1;i>=0;i--){
   save=i;
   v=data[i];
   for(;;){
     j=save+save+1;
     if(j>n-1){ break; }
     if( (j!=n-1)&&(data[j+1]>data[j]) ){
       j++;
     }
     if(v>=data[j]){ break; }
     data[save]=data[j];
     save=j;
   }
   data[save]=v;
 }
 for(i=n-1;i>0;i--){
   swap(data[0],data[i]);
   save=0;
   v=data[0];
   for(;;){
     j=save+save+1;
     if(j>i-1){ break; }
     if( (j!=i-1)&&(data[j+1]>data[j]) ){
       j++;
     }
     if(v>=data[j]){ break; }
     data[save]=data[j];
     save=j;
   }
   data[save]=v;
 }

[編集] 特徴

データの出現順序による計算量の変化が小さい（クイックソートでは最悪の場合O $(n^2)$ となってしまう）^[1]。ただし、平均的にはクイックソートより遅い^[1]。
ソート対象のデータ自体以外に必要となる作業領域の大きさは固定で、データ量に依存しない。

ただし以下のように、現代のコンピュータで用いられる高速化技法に適さない特徴があることにも注意する必要がある。

並列化できない。
ヒープ構造はメモリへのアクセスが連続しておらず、ランダムアクセスになる。すなわち、空間的局所性が低い。

[編集] 脚注

[ヘルプ]

^ ^a ^b ^c ^d ^e 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、220-221頁。ISBN 4-87408-414-1。

[編集] 関連項目

イントロソート

[編集] 参考文献

ジョン・ベントリー『珠玉のプログラミング』小林健一郎訳、ピアソン・エデュケーション、2000年、ISBN 4-89471-236-9。

[編集] 外部リンク

Heapsort code

[algo-0] 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、220-221頁。ISBN 4-87408-414-1。

[1]