アルゴリズムとデータ構造編【整列】 第8章 ヒープソート

先頭へ戻る

この章の概要

この章の概要です。

関連する話題が、以下のページにあります。

ヒープソート

この章では、ヒープソートを取り上げます。

ヒープソートは、ヒープというデータ構造を利用したアルゴリズムです。 ヒープについては、【データ構造】第9章で解説しているので、そちらを参照して下さい。

ヒープというデータ構造は、要素の挿入と、最小値(または最大値)を持った要素の参照が高速に行えるという特性があります。 従って、ソートしたいデータ列をヒープへ挿入していき、最小値(または最大値)を持った値を順次取り出していけば、 効率良く、ソートされた結果を得られる訳です。

プログラム例

ヒープソートの実装は、【データ構造】第9章で解説したヒープのコードをそのまま利用するだけです。

#include <stdio.h>
#include "ppps_int_heap.h"

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void heap_sort(int* array, size_t size);
static void print_array(const int* array, size_t size);

int main(void)
{
	int array[] = {7, 2, 9, 6, 4, 3, 8, 1, 5};

	print_array( array, SIZE_OF_ARRAY(array) );
	heap_sort( array, SIZE_OF_ARRAY(array) );
	print_array( array, SIZE_OF_ARRAY(array) );

	return 0;
}

/*
	ヒープソート (昇順)
*/
void heap_sort(int* array, size_t size)
{
	PPPSIntHeap heap;
	size_t i;

	heap = ppps_int_heap_create( size );

	/* データをヒープへ格納 */
	for( i = 0; i < size; ++i ){
		ppps_int_heap_insert( heap, array[i] );
	}

	/* データを根から順に取り出す */
	for( i = 0; i < size; ++i ){
		ppps_int_heap_remove_root( heap, &array[i] );
	}

	ppps_int_heap_delete( heap );
}

/*
	配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
	size_t i;

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

実行結果:

7 2 9 6 4 3 8 1 5
1 2 3 4 5 6 7 8 9

単に、ソート対象の配列の要素をヒープへ格納した後、根から順番に取り出すだけです。 ヒープ自体の実装ができていれば、非常に簡単です。

しかし、このプログラムには少し問題があります。 それは、ソート対象の配列以外に、ヒープのための領域を取ってしまうことです。 ヒープの実装も配列ですから(【データ構造】第9章参照)、 単純にいって、メモリを2倍使ってしまうということです。
この問題の解決を試みましょう。

メモリを浪費しない実装

まず、前の項で使ったサンプルプログラムで使っている ppps_int_heap.c の実装を見ておいて下さい。

余計なメモリを浪費してしまうのは、ppps_int_heap_create関数の中で、ヒープを実装するために配列を動的に確保しているためです。 ソート対象自体が同じ大きさの配列なのですから、ソート対象自身をヒープとして取り扱えば、余計なメモリを使わなくて済みます。
また、既に要素が格納されている配列をヒープとして取り扱うのであれば、ppps_int_heap_insert関数を呼び出す必要もありません。

では、ppps_int_heap の実装を踏まえつつ、1つのソースファイル内にコードをまとめてみます。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

/* ヒープ */
struct Heap_tag {
	int*   data;           /* データ本体 */
	int    capacity;       /* 最大容量 */
	int    first_empty;    /* 空になっている最初の位置 */
};
typedef struct Heap_tag Heap;

static void heap_sort(int* array, size_t size);
static void init_heap(Heap* heap, int* array, size_t size);
static void down_heap(Heap* heap, int root, int end);
static void sort_heap(Heap* heap);
static void print_array(const int* array, size_t size);

int main(void)
{
	int array[] = {0, 7, 2, 9, 6, 4, 3, 8, 1, 5};

	print_array( array + 1, SIZE_OF_ARRAY(array) - 1 );
	heap_sort( array, SIZE_OF_ARRAY(array) );
	print_array( array + 1, SIZE_OF_ARRAY(array) - 1 );

	return 0;
}

/*
	ヒープソート (昇順)
*/
void heap_sort(int* array, size_t size)
{
	Heap heap;

	init_heap( &heap, array, size );
	sort_heap( &heap );
}

/*
	ヒープを初期化
*/
void init_heap(Heap* heap, int* array, size_t size)
{
	int root;

	heap->data = array;
	heap->capacity = size - 1;
	heap->first_empty = size;

	/* ヒープを再構成 */
	for( root = size / 2; root > 0; --root) {
		down_heap( heap, root, heap->first_empty - 1 );
	}
}

/* ヒープの指定要素を適切な位置まで沈める */
void down_heap(Heap* heap, int root, int end)
{
	while( root * 2 <= end ){
		int child = root * 2;  /* 左の子の位置 */

		/* 2つの子があるなら、小さい方を使う */
		/* 右の子の添字は、左の子の添字 + 1 である */
		if( child + 1 <= end ){
			if( heap->data[child] > heap->data[child + 1] ){
				child = child + 1;
			}
		}

		/* 子との大小関係が逆なら、入れ替える */
		if( heap->data[child] < heap->data[root] ){
			SWAP( int, heap->data[child], heap->data[root] );
			root = child;
		}
		else {
			break;
		}
	}
}

/* ヒープ内をソートする */
void sort_heap(Heap* heap)
{
	int end = heap->first_empty - 1;

	while( end > 0 ){
		SWAP(int, heap->data[1], heap->data[end]);
		end--;
		down_heap( heap, 1, end );
	}
}

/*
	配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
	size_t i;

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

実行結果:

7 2 9 6 4 3 8 1 5
9 8 7 6 5 4 3 2 1

できるだけ素直に ppps_int_heap の処理を持ってきました。
まず、init_heap関数で、ソート対象配列をヒープ化しています。 ここでは、ヒープとして正しい要素の並びになるように、down_heap関数を繰り返し呼び出しています。 子を持った要素1つ1つに注目し、自分の値と子の値の大小関係が逆転したら入れ替えることを繰り返します。

実際にソートを行うには、sort_heap関数を呼び出します。 これは、根と末尾の要素を入れ替えて、根に来た要素を適切な位置まで沈めることを繰り返して実現します。 末尾の位置を1つずつ手前へ手前へと移動させていくことで、ヒープの最後尾から順番に小さい値が確定していきます。


さて、ソートが昇順でなくて、降順で行われていますが、これはヒープを構築する際の大小関係の判定を逆にすれば修正できます。 具体的には、down_heap関数内の2か所を書き換えます。

/* ヒープの指定要素を適切な位置まで沈める */
void down_heap(Heap* heap, int root, int end)
{
	while( root * 2 <= end ){
		int child = root * 2;  /* 左の子の位置 */

		/* 2つの子があるなら、大きい方を使う */
		/* 右の子の添字は、左の子の添字 + 1 である */
		if( child + 1 <= end ){
			if( heap->data[child] < heap->data[child + 1] ){
				child = child + 1;
			}
		}

		/* 子との大小関係が逆なら、入れ替える */
		if( heap->data[child] > heap->data[root] ){
			SWAP( int, heap->data[child], heap->data[root] );
			root = child;
		}
		else {
			break;
		}
	}
}

ppps_int_heap.c の同じ箇所と、up_heap関数を同じように書き換えると、ヒープの根が最大値となる実装に変わるので、 根を取り出すことを繰り返したときの結果が降順になってしまいます。

性能

性能を確認しておきましょう。 ここでは同じ O(n log n) の計算量を持ったクイックソート、マージソートと比較してみます。 アルゴリズムの実装には、コードライブラリの ppps_int_sort を使い、 それぞれ非再帰版を使用します。

#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#include "ppps_int_sort.h"

#define ARRAY_SIZE              100000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void init_array(int* array, size_t size);

int main(void)
{
	int array[ARRAY_SIZE];
	
	
	init_array( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_BEGIN(1);
	ppps_heap_sort( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_END("ppps_heap_sort");

	init_array( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_BEGIN(1);
	ppps_merge_sort_no_recursive( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_END("merge_sort_no_recursive");

	init_array( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_BEGIN(1);
	ppps_quick_sort_no_recursive( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_END("quick_sort_no_recursive");

	return 0;
}

/*
	配列を初期化
*/
void init_array(int* array, size_t size)
{
	size_t i;

	srand(0);

	for(i = 0; i < size; ++i){
		array[i] = rand() % size;
	}
}

要素数を変えて実測した結果、次のようになりました。

データ件数 ヒープソート マージソート クイックソート
10,000個 0.003秒 0.003秒 0.003秒
100,000個 0.042秒 0.038秒 0.021秒
1,000,000個 0.494秒 0.353秒 0.248秒
10,000,000個 7.63秒 3.858秒 2.147秒

3つのアルゴリズムは、いずれも O(n log n) の計算量ですが、 上記のように、ヒープソート>マージソート>クイックソート という順番で時間が掛かることが分かります。

まとめ

ヒープソートの計算量は O(n log n) です。 これは、クイックソート(第6章)やマージソート(第7章)と同じですが、 通常は、マージソートの2倍程度遅いため、一番低速になります。
また、マージソートと同様に、データの並びに影響を受けず、常に O(n log n) の計算量を保てる利点があります。

マージソートで配列をソートするときのような、作業用のメモリを必要とすることがなく、メモリ消費の面でも優れていますが、 安定なソートではないことに注意が必要です。


練習問題

問題① 「プログラム例」のサンプルプログラムを、降順にソートした結果を得るように修正して下さい。


解答ページはこちら

参考リンク

更新履歴

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2013/2/9 新規作成。





前の章へ(第7章 マージソート)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS