ヒープソート Heap Sort【可視化GIFでソートアルゴリズムを解説 その７】

ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである（ヒープ領域とは無関係であることに注意する）。ヒープはほぼ完全な二分木構造であると同時に、累積の性質を満たします。つまり、子ノードのキー値またはインデックスは常にその親ノードよりも小さい（または大きい）です。

7.1 アルゴリズムの説明

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

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

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

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

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

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

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

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

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

7.2 可視化デモ

7.3 実装

注：ここでは、完全な二分木の性質の一部が使用されています

//グローバル変数を宣言して、配列の長さを記録します。
static int len;

    /**
     * ヒープソート
     *
     * @param array
     * @return
     */
    public static int[] HeapSort(int[] array) {
        len = array.length;
        if (len < 1) return array;
        //1.最大ヒープを構築する
        buildMaxHeap(array);
        //2.ヒープの最初の位置（最大値）と最後の位置がループで交換され、次に
        while (len > 0) {
            swap(array, 0, len - 1);
            len--;
            adjustHeap(array, 0);
        }
        return array;
    }
    /**
     * 最大ヒープを構築する
     *
     * @param array
     */
    public static void buildMaxHeap(int[] array) {
        //最後の非リーフノードから始まり、上に向かって最大ヒープを構築する
        for (int i = (len/2 - 1); i >= 0; i--) {
            adjustHeap(array, i);
        }
    }

    /**
     * 最大のヒープになるように調整する
     *
     * @param array
     * @param i
     */
    public static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        //左側のサブツリーがあり、左側のサブツリーが親ノードよりも大きい場合、最大のポインターは左側のサブツリーを指す
        if (i * 2 < len && array[i * 2] > array[maxIndex])
            maxIndex = i * 2;
        //右側のサブツリーがあり、右側のサブツリーが親ノードよりも大きい場合、最大のポインターは右側のサブツリーを指す
        if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
            maxIndex = i * 2 + 1;
        //親ノードが最大値でない場合は、親ノードを最大値と交換し、親ノードとの交換位置を再帰的に調整する
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
    }

7.4 性能評価

• 最良時間計算量：T(n) = O(nlogn)
• 最悪時間計算量：T(n) = O(nlogn)
• 平均時間計算量：T(n) = O(nlogn)

---