ヒープソート [Heap Sort]

ヒープソートは整列の対象となる配列の中でヒープ構造を構築しながら整列を行うアルゴリズムです。

整列させたい配列からヒープを構築して、そこから元の配列にコピーして整列を完了させるのではないのです。マージソートのように作業用の領域や、クイックソートのような再帰処理が必要ありません。

アルゴリズム分析

まずは以下のような手順ではないことを理解してください。

1. 整列対象の配列から別領域にヒープを構築する
2. ヒープから元の配列にデータをコピーする

この方法だとヒープを構築する専用の領域が必要になります。

実際のヒープソートは以下のような手順です。整列対象の配列はN個のデータを持ち、インデックスは1からNとします。

1. 整列対象の配列内にボトムアップでヒープを構築する
2. 構築されたヒープの先頭要素[1]と最後の要素[N]を交換する
3. 要素[1]から要素[N-1]でヒープを再構成する
4. ヒープの先頭要素[1]と最後の要素[N-1]を交換する
5. 手順3.に戻る
   • 手順4.にある最後の要素は[N-2],[N-3]...と移動する
6. ヒープ構造がなくなれば整列完了

ヒープのルート要素を配列の末尾の要素へ移動することで整列が行われるのです。

特徴

ヒープソートは整列対象の配列内でヒープを構築するので整列のための特別な作業領域を必要としないのが特徴です。処理速度はクイックソートなどに劣りますが、膨大なセットを整列させたい場合に作業領域を節約できるので結果的に効率の良いソートが実現できます。

実際のプログラミングではデータを交換するための小さな領域などは使います。

サンプルコード

C言語

配列を昇順に整列させます。

void heapSort(int numbers[], int array_size)
{
    int i, temp;

    /* ボトムアップでヒープを構築 */
    for (i = (array_size / 2) - 1; i >= 0; i--)
    {
        siftDown(numbers, i, array_size);
        printf("[%d]\n", i);
        print_data(numbers, MAX_SIZE);
    }

    /* ヒープソート実行 */
    for (i = array_size - 1; i >= 1; i--)
    {
        temp = numbers[0];
        numbers[0] = numbers[i];
        numbers[i] = temp;
        siftDown(numbers, 0, i - 1);
    }
}

/**
ヒープの先頭要素を適切な位置へ沈める
(配列の特定の領域を対象にヒープを構築する)
*/
void siftDown(int numbers[], int root, int bottom)
{
    int done, maxChild, temp;

    done = 0;
    while ((root * 2 <= bottom) && (!done)) {
        if (root * 2 == bottom) {
            maxChild = root * 2;
        } else if (numbers[root * 2] > numbers[root * 2 + 1]) {
            maxChild = root * 2;
        } else {
            maxChild = root * 2 + 1;
        }

        if (numbers[root] < numbers[maxChild]) {
            temp = numbers[root];
            numbers[root] = numbers[maxChild];
            numbers[maxChild] = temp;
            root = maxChild;
        } else {
            done = 1;
        }

    }
}