ヒープソート

アルゴリズム

ヒープ構造は、ポインタ等の制御用データが不要で、データ自体の並び順（配列）だけで表現できるという利点がある。ヒープソートを実装する際にはこの利点を生かし、元のデータ領域をそのままヒープ構造や整列済みリストに転用するインプレースなソートとして実装することが多い。
最初に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 voidswap(double arr[], int a, int b){
    double tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;}voidheapsort(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 voidupheap(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 voiddownheap(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;
    }}

補足

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