ヒープソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=[[Image:Sorting heapsort anim.gif]]
|caption=ヒープソートのアルゴリズムがランダムな数字の列に対して動作する例。アルゴリズムの第一ステージでは、配列の要素を[[二分ヒープ|ヒープ条件]]を満すように並べている。その後、実際にソート済みの場所に並びかえる前に、ヒープ構造がイラストの上に表れている。
|data=[[配列]]
|time=<math>O(n\text{ }\log\text{ }n)</math>
|average-time=<math>O(n\text{ }\log\text{ }n)</math>
|best-time=<math>\Omega(n)</math><ref>https://doi.org/10.1006/jagm.1993.1031</ref>
|space=<math>O(1)</math> auxiliary
|optimal=Never
}}
'''ヒープソート''' ('''heap sort''') とはリストの並べ替えを[[二分ヒープ]]木を用いて行う[[ソート]]の[[アルゴリズム]]である<ref name="algo">{{cite book | 1=和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | pages=220-221 | isbn=4-87408-414-1}}</ref>（[[ヒープ領域]]とは無関係であることに注意する）。

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

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

計算量は [[ランダウの記号|O]]<math>(n \log n)</math> となる<ref name="algo" />。[[安定ソート]]ではない<ref name="algo" />。

== アルゴリズム ==
ヒープ構造は、ポインタ等の制御用データが不要で、データ自体の並び順（配列）だけで表現できるという利点がある。ヒープソートを実装する際にはこの利点を生かし、元のデータ領域をそのままヒープ構造や整列済みリストに転用するインプレースなソートとして実装することが多い。

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

[[ファイル:Heap sort algorithm-phase1.svg|right|300px]]
まず各データをヒープ構造に登録していく。m個のデータを処理した状態では、添字1 〜 mがヒープ構造で、(m + 1) 〜 Nが未整列リストとなる。m + 1個目のデータを取り出し、ヒープ構造に登録する。このとき構成するヒープは、昇順にソートする場合はルートが最大値になるよう、降順にソートする場合はルートが最小値になるよう構成する。

[[ファイル:Heap sort algorithm-phase2.svg|right|300px]]
すべてのデータをヒープ構造に登録し終えたら、ヒープからの取り出しに移る。ヒープのルートを取り出し、配列の後ろから詰めていく。mを Nから1まで減しながら、取り出したルート要素を配列の添字mに置く。すなわち、(N - m)個のデータを取り出した状態では添字1 〜 mがヒープ構造であり、m + 1 〜 Nが整列済みリストとなる。

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

ヒープの操作の具体的な実装については、[[二分ヒープ]]の記事を参照すること。

また、一般のヒープ操作では、根元側から木を成長させるのが普通だが、配列のようなデータ構造のヒープソートで、あらかじめ木の最終的な大きさがわかっている場合は、木の葉の側から順番にヒープを構築すると、より効率が良い（この記事で示す実装例では使っていない）。
<!--以下の例には問題がある。通常ヒープソートで再帰は使わない--><!--
=== 例 ===
[[ファイル:Binary heap indexing.png|thumb|right|250px|ヒープの木構造表現]]
ヒープソートでは、まずデータの格納されている[[配列]]を右の画像のような[[木構造 (データ構造)|木構造]]（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
という数字を昇順にソートする場合を考えてみる。この例を木構造で表すと、
[[ファイル:Heap_example1.png|center|300px]]
のようになる。この木をヒープの条件を満たすようにする。すなわち全てのノードの子はその親より小さい値になるようにする。これは
* ノードが子を持っていないならそのまま。
* ノードが一つしか子を持っていないなら子と自分の値を比べて子の方が大きいなら入れ換える。
* ノードが二つの子を持つ場合
*# 両者の子以下の木構造をヒープ構造に変換する（[[再帰呼び出し]]で行う）。
*# 自分の値と二つの子の値を比べて、最も大きい値が子の場合入れ換える。
*# 入れ換えが起きたなら、入れ換えが起きた方の子以下の木構造をもう一度ヒープ構造に変換する。
という処理を再帰的に行うことでヒープ構造が生成される。dataの例では
[[ファイル:Heap_example2.png|center|300px]]
という形になる。このとき根の値（ここでは12）がこの配列の最大値である。そこで根と配列としたとき最も端の値（ここでは1が入っている場所）を入れ換えると下のようになる。（12は整列済みになったので木構造から外す。）

[[ファイル:Heap_example3.png|center|300px]]
今度は木構造の要素の数を 11にして同じ事を繰り返す。すると今度は根に11（残った要素での最大値）が来るのでまた根と端（配列として11番目の場所）を入れ換えてやはり要素の数を1つ減らして同様の処理を繰り返す。これを要素が1になるまで繰り返すと配列の内部は
 data[1 .. 12] = 1 2 3 4 5 6 7 8 9 10 11 12
と整列した形になる。
-->
=== 実装例 ===
<syntaxhighlight lang="c">
static void upheap(double arr[], int n);
static void downheap(double arr[], int n);

static inline void
swap(double arr[], int a, int b)
{
    double tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

void
heapsort(double arr[], int n_elems)
{
    int i = 0;

    /*
     * arr の先頭から順に、ヒープを成長させる
     *  0    1    2  | 3    4    5
     * [  ] [  ] [  ]|[  ] [  ] [  ]
     *    ヒープ     |   未処理の入力
     *              ===>
     * i は、ヒープ中の要素数であると同時に、未処理データの先頭を
     * 指してもいる
     */
    /* 配列が全部ヒープに入れ替わるまで繰り返す */
    while (++i < n_elems) {
        /*
         * 配列の先頭要素を、ヒープの最後に移動するわけだが、どちらも
         * ちょうど同じ場所に最初からあるので、境界を移動させるだけでよい
         */

        /*
         * arr[i] に、ヒープに新しく追加されたデータがあるものとして、
         * 先頭から arr[i] までがヒープになるよう再構成する
         */
        upheap(arr, i);
    }

    /*
     * arr の末端から順に、ヒープから取り出して並べる
     *  0    1    2  | 3    4    5
     * [  ] [  ] [  ]|[  ] [  ] [  ]
     *    ヒープ     |   ソート済みの配列
     *             <===
     */
    /* ヒープが全部配列に入れ替わるまで繰り返す */
    while (--i > 0) {
        /*
         * ヒープの先頭要素を、配列に移動すると同時に、ヒープの最後の
         * 要素を、ヒープの先頭に移動する swap
         */
        swap(arr, 0, i);

        /*
         * arr[0] に、ヒープの最後から移動されたデータがあるものとして、
         * 先頭から arr[i - 1] までがヒープになるよう再構成する
         */
        downheap(arr, i);
    }
}

/*
 * macros for heaptree
 * for 0 origin array
 */
#define LEFT_CHILD(i)  (((i) + 1) * 2 - 1)
#define RIGHT_CHILD(i) (((i) + 1) * 2)
#define PARENT(i)      (((i) + 1) / 2 - 1)

/*
 * arr[n] に、ヒープに新しく追加されたデータがあるものとして、
 * 先頭から arr[n] までがヒープになるよう再構成する
 */
static void
upheap(double arr[], int n)
{
    while (n > 0) {
        int m = PARENT(n);

        if (arr[m] < arr[n]) {
            swap(arr, m, n);
        } else {
            break;
        }

        n = m;
    }
}

/*
 * arr[0] に、ヒープの最後から移動されたデータがあるものとして、
 * 先頭から arr[n - 1] までがヒープになるよう再構成する
 */
static void
downheap(double arr[], int n)
{
    int m = 0;
    int tmp = 0;

    for (;;) {
        int l_chld = LEFT_CHILD(m);
        int r_chld = RIGHT_CHILD(m);

        if (l_chld >= n) {
            break;
        }

        if (arr[l_chld] > arr[tmp]) {
            tmp = l_chld;
        }
        if ((r_chld < n) && (arr[r_chld] > arr[tmp])) {
            tmp = r_chld;
        }

        if (tmp == m) {
            break;
        }
        swap(arr, tmp, m);

        m = tmp;
    }
}
</syntaxhighlight>
<!--
[[擬似コード]]で表すとヒープソートは以下のようになる。

 '''ヒープ構造へ変換する'''
 '''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の実装は上記同様省略する。

<code>
  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;
  }
</code>
-->
==== 補足 ====
ここで示した実装では原理と一般的な手法を示すため、細かいチューニングはしていない。ルートの要素を番兵にして比較を節約する、スワップではなくループの外で定義した一時変数に退避するようにして無用な「書いたものを読んで」を減らす、最初からヒープの最終的な大きさがわかっているので、木を葉のほうから構築する、といった改善が可能な点がある（参考文献『珠玉のプログラミング』の該当コラムの「問題」の節と巻末の解説を参照のこと）。

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

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

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

== 脚注 ==
{{脚注ヘルプ}}
{{reflist}}


== 関連項目 ==
* [[イントロソート]]

== 参考文献 ==
* ジョン・ベントリー 『珠玉のプログラミング』（コラム14）小林健一郎訳、ピアソン・エデュケーション、2000年、ISBN 4-89471-236-9。

== 外部リンク ==
*[http://www.algorithm-code.com/wiki/Heapsort Heapsort code]

{{ソート}}
{{DEFAULTSORT:ひいふそおと}}
[[Category:ヒープ]]
[[Category:ソート]]

[[no:Sorteringsalgoritme#Heap sort]]