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

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

アルゴリズム分析

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

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

    }
}

ヒープソートのデモンストレーション プログラム: heap_sort.c

Python

def heapsort(aList):
    list_size = len(aList) - 1
    for i in range((list_size / 2), -1, -1):
        shift_down(aList, i, list_size)

    for i in range(list_size , 0, -1):
        if aList[0] > aList[i]:
            temp = aList[0]
            aList[0] = aList[i]
            aList[i] = temp
            shift_down(aList, 0, i - 1)
    return aList

def shift_down(aList, root, bottom):
    while (root * 2) <= bottom:
        if (root * 2) == bottom:
            maxChild = root * 2
        elif aList[root * 2] > aList[(root * 2) + 1]:
            maxChild = root * 2
        else:
            maxChild = root * 2 + 1

        if aList[root] < aList[maxChild]:
            temp = aList[root]
            aList[root] = aList[maxChild]
            aList[maxChild] = temp
            root = maxChild
        else:
            return


if __name__ == '__main__':
    from random import shuffle
    l = range(15)
    lcopy = l[:]
    shuffle(l)
    print('Unsorted')
    print l
    assert l != lcopy
    print ('Sorted')
    print heapsort(l)
    assert l == lcopy