C言語によるヒープソートの実装

サンプルプログラム

ここでは実際に、C言語によるヒープソートの実装を見てみることにします。ここえは、あえてヒープの木構造を作らず、配列の中に擬似的に木構造を作ってソートを行う例を紹介します。

配列の要素番号が１からスタートすると仮定し、n番目のノードの子ノードは、2n、および2n+1であるような構造を持つバイナリツリー構造を仮定します。いま、配列の大きさがNであるとします。すると、配列の要素は1番目からN番目まで存在することになります。

すると、このとき、配列を逆からたどって、自らの親ノードの値と、自分の値を比較し、交換の必要があれば、交換を行います。

この処理が一通り終わると、要素１には、行列内の最大値が来るようになります。今度は、要素2からN番目までの、N-1個の行列に対し、同様の処理を行うと、2番目に、2からN-1番目までの最大値が来るようになります。以上のような処理を、繰り返せば、最終的に、降順でデータの並べ替えが完了します。

理論上は、配列の大きさがNであれば、N-1回この処理を繰り返せば、処理が完成することになります。

サンプルプログラム

以上の考え方を実装すると、以下のプログラムのようになります。入力して実行してみてください。

listex7-heap:main.c 
#include <stdio.h>
#include <stdlib.h>

//	配列の最大値
#define MAX_LENGTH	5

//	配列aに登録されている要素の個数（

void swap(int*,int,int);
int downheap(int*,int,int);
void showData(int*,int);
void heap_sort(int*,int);

void main(){
	//	ソートする行列(最初は０にしておく
	int array[MAX_LENGTH+1] = { 0,4,2,5,6,1 };
	//	ソートする処理
	heap_sort(array,MAX_LENGTH);
}

//	配列の成分の入れ替え
void swap(int* pArray,int m,int n)
{
	int tmp = pArray[m];
	pArray[m] = pArray[n];
	pArray[n] = tmp;
}
//	ヒープの要素を沈める処理。pArray[start]から、pArray[end]までを要素とする。
int downheap(int* pArray,int start,int end){
	int parent,child,r = 0;
	child = end;	//	子ノードのスタート位置
	//	末端の要素から、たどり、親要素よりも値が大きければ、入れ替える処理を繰り返す。
	do{
		//	親ノードの番号取得
		parent = start + (child - start) / 2;
		//	バイナリツリーの末端の最初が親よりも大きければ、入れ替える。
		if(pArray[child] > pArray[parent]){
			swap(pArray,child,parent);
			r = 1;
		}
		//	iをデクリメント
		child--;
	}while(parent > start);	//	子ノードが、startの位置を超えてしまったら、終了
	return r;
}

//  配列の表示
void showData(int* pArray,int length){
    int i;
    for(i = 1; i < length+1; i++){
        printf("%d ",pArray[i]);
    }
    printf("\n");
}

//	ヒープソート
void heap_sort(int* pArray,int size)
{
	int i = 1;
	showData(pArray,size);
	while(downheap(pArray,i,size)){
		//	途中経過を出力
		showData(pArray,size);
		i++;
	}
}
実行結果
4 2 5 6 1
6 4 5 2 1
6 5 4 2 1