C言語アルゴリズム-ヒープソート

ヒープソート (heap sort)

ヒープソートとは

ヒープソートとは、データ列をヒープ構造に構成しておき、ヒープ構造の先頭データを取り出していくことで整列するアルゴリズムです。ヒープソートは、二分ヒープ木を用いて行うソートであることからヒープの名前が付いています。なお、プログラムなどにおけるヒープ領域とは無関係です。

ヒープ（heap）とは

ヒープとは、「半順序木 (partial ordered tree) 」を配列で実現したデータ構造です。「半順序木」の構造とは、２分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さく（または大きく）なるように作られたデータ構造です。

親ノードは子ノードより大きいか等しいものを「最大ヒープ（max-heap property）」、親ノードは子ノードより小さいか等しいものを「最小ヒープ（min-heap property）」といいます。

親の添字を「k」とすると、その子の添字は「2*k+1」及び「2*k+2」になります。

子の添字を「k」とすると、その親の添字は「(k - 1) / 2」になります。


TABLE : [10 20 30 40 50 60 70]
(index)   0  1  2  3  4  5  6

        (root)
          10(0)
       ／       ＼ 
    20(1)       30(2)
  ／   ＼       ／  ＼ 
40(3)  50(4) 60(5)  70(6)

ヒープソートの整列過程

ヒープソートのアルゴリズムは、以下の通りです。

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

以下は「降順のヒープ構造を生成　→　根を取り出す　→　降順のヒープ構造を生成」を繰り返すことで整列するデータの流れです。


[before]: 2 5 3 6 1 4 7 
[heap]  :(7 6 4 5 1 2 3)
[heap]  :(6 5 4 3 1 2) -> [7] 
[heap]  :(5 3 4 2 1)   -> [6 7]
[heap]  :(4 3 1 2)     -> [5 6 7] 
[heap]  :(3 2 1)       -> [4 5 6 7] 
[heap]  :(2 1)         -> [3 4 5 6 7] 
[heap]  :(1)           -> [2 3 4 5 6 7] 
[after] : 1 2 3 4 5 6 7

ヒープソートの性能

計算量はO(n log n)なのですが、平均的にはクイックソート・マージソートよりも通常遅くなります。また、安定ソートではありません。

ただし、最悪計算量でもO(n log n)なので、クイックソートよりも応用範囲が広いといえます。

C言語によるヒープソートのプログラム


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*!
 * @brief       配列にランダムな数値を格納する。
 * @param[out]  array  数値格納先の配列
 * @param[in]   size   配列のサイズ
 * @param[in]   digit  数値の桁数。
 */
static void
array_random_number(int *array, unsigned int size, unsigned int digit)
{
    int i;

    /* 起動毎に異なる乱数を発生させる */
    srand((unsigned int)time(NULL));
    for(i = 0; i < size; i++){
        array[i]=rand() % digit;
    }
}

/*!
 * @brief       配列内容を表示する
 * @param[in]   array  数値格納先の配列
 * @param[in]   size   配列のサイズ
 */
static void
array_print(int *array, unsigned int size)
{
    int i = 0;

    for(i = 0; i < size; i++){
        printf("%d ", array[i] );
    }
    putchar('\n');
}

/*!
 * @brief      要素要素を入れ替える
 * @param[in]  i  要素位置
 * @param[in]  j  要素位置
 */
static void
swap(int *i, int *j)
{
    int temp;

    temp = *i;
    *i   = *j;
    *j   = temp;
}

/*!
 * @brief          降順の半順序木（ヒープ）を作成する
 * @param[in/out]  array  整列する要素配列
 * @param[in]      left   根とみなす要素位置
 * @param[in]      right  配列上の子に該当する要素位置
 */
static void
down_heap(int *array, int left, int right)
{
    int child;
    int parent = left;
    int temp = array[left];  /* 根とみなす */
    int cl, cr;

    /* 子を持っている限り繰り返す */
    while(parent < (right + 1) / 2){
        cl = parent * 2 + 1;  /* 左の子 */
        cr = cl + 1;          /* 右の子 */

        /* 大きい方の子を選択する */
        if((cr <= right) && (array[cr] > array[cl])){
            child = cr;
        }else{
            child = cl;
        }

        /* 子の方が大きい場合には交換する */
        if(temp >= array[child]) break;
        array[parent] = array[child];
        parent = child;
    }
    array[parent] = temp;
}

/*!
 * @brief          ヒープソートを行う。
 * @param[in/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 */
void
heap_sort(int *array, unsigned int size)
{
    int i;

    /* 半順序木を構成する */
    for(i = (size - 1) / 2; i >= 0; i--){
        down_heap(array, i, size - 1);
    }
    printf("[heap]  :"); array_print(array, size);

    /* ソート */
    for (i = size - 1; i > 0; i--) {
        /* 半順序木の根と末尾の要素を交換する */
        swap(&array[0], &array[i]);

        /* 根を外したデータ列で、半順序木を構成する */
        down_heap(array, 0, i - 1);
        printf("[heap]  :"); array_print(array, i);
    }
}

int
main(void)
{
    int data[15];
    array_random_number(data, sizeof(data)/4, 100);

    printf("[before]:"); array_print(data, sizeof(data)/4);

    heap_sort(data, sizeof(data)/4);

    printf("[after] :"); array_print(data, sizeof(data)/4);

    return(0);
}