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

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

アルゴリズム分析

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

  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言語

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

/*
 * ヒープソート
 * @param numbers ソートする配列
 * @param array_size 配列のサイズ
 */
void heap_sort(int* numbers, int array_size)
{
    int i, temp;

    // ヒープ構築
    // 二分木なので親ノードのインデックスは
    // (n - 1) / 2 となる
    for (i = (array_size - 1) / 2; i >= 0; i--)
    {
        max_heap(numbers, i, array_size);
    }

    // ヒープソート実行
    // 値を昇順に並べる。
    //
    // 先頭要素(最大値)を配列の最後に移動させて
    // 最後の要素を無視してヒープを構築すると
    // 配列内で最も小さな値から順に並ぶ
    for (i = array_size - 1; i > 0; i--)
    {
        temp = numbers[0];
        numbers[0] = numbers[i];
        numbers[i] = temp;
        max_heap(numbers, 0, i - 1);
    }

}

/*
 * Max-heap を構築する。
 *
 * 親ノードは子ノードより大きいか等しくなる。
 *
 * @param numbers ヒープの配列
 * @param root ヒープの先頭要素のインデックス
 * @param bottom ヒープの最後の要素のインデックス
 */
void max_heap(int* numbers, int root, int bottom)
{
    // 子ノードのインデックス
    // 配列の先頭要素のインデックスが 0 なので
    // 子ノードは 2n + 1 と 2n + 2 で計算する
    int l_idx = (root * 2) + 1;
    int r_idx = (root * 2) + 2; 

    // 最大値を持つ要素のインデックス
    int maxChild;

    if (l_idx <= bottom && numbers[l_idx] > numbers[root]) {
        maxChild = l_idx;
    } else {
        maxChild = root;
    }

    if (r_idx <= bottom && numbers[r_idx] > numbers[maxChild]) {
        maxChild = r_idx;
    }

    if (maxChild != root) {
        int temp = numbers[root];
        numbers[root] = numbers[maxChild];
        numbers[maxChild] = temp;
        // 配列の先頭要素には最大値を持つ要素のインデックスを指定する
        max_heap(numbers, maxChild, bottom);
    }

}

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

Python

def heapsort(aList):
    list_size = len(aList) - 1
    for i in range((list_size / 2), -1, -1):
        sift_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
            sift_down(aList, 0, i - 1)
    return aList
# end def heapsort


def sift_down(aList, root, bottom):
    left = root * 2 + 1
    right = root * 2 + 2
    
    if left <= bottom and aList[left] > aList[root]:
        max_child = left
    else:
        max_child = root
    
    if right <= bottom and aList[right] > aList[max_child]:
        max_child = right
    
    if max_child != root:
        aList[root], aList[max_child] = aList[max_child], aList[root]
        sift_down(aList, max_child, bottom)
# end def sift_down

if __name__ == '__main__':
    from random import randint
    l = [randint(0,999) for i in range(7)]
    print('Unsorted')
    print l

    print ('Sorted')
    print heapsort(l)

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