ヒープソート

ヒープソート

ヒープソートのアルゴリズムがランダムな数字の列に対して動作する例。アルゴリズムの第一ステージでは、配列の要素をヒープ条件を満すように並べている。その後、実際にソート済みの場所に並びかえる前に、ヒープ構造がイラストの上に表れている。
クラス	ソート
データ構造	配列
最悪計算時間	$O(n{\text{ }}\log {\text{ }}n)$
最良計算時間	$\Omega (n)$
平均計算時間	$O(n{\text{ }}\log {\text{ }}n)$
最悪空間計算量	$O(1)$ auxiliary

ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである（ヒープ領域とは無関係であることに注意する）。

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

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

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

アルゴリズム

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

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

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

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

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

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

また、一般のヒープ操作では、根元側から木を成長させるのが普通だが、配列のようなデータ構造のヒープソートで、あらかじめ木の最終的な大きさがわかっている場合は、木の葉の側から順番にヒープを構築すると、より効率が良い（この記事で示す実装例では使っていない）。

実装例

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;
    }
}

補足

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

特徴

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

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

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

関連項目

• イントロソート

参考文献

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

外部リンク

• Heapsort code