#include <stdio.h>
#include <stdlib.h>	/* 疑似乱数生成時に必要 */
#include <time.h>	/* 実行毎に異なる疑似乱数を発生させる為必要 */

/* マクロ定義 */
#define NUM_DATA 10	/* 要素数 */

/* グローバル変数 */
int a[ NUM_DATA ];

/* プロトタイプ宣言 */
void SetData();			/* データを作成 */
void ShowData();		/* ヒープを構成する */
void HeapMain( int n );		/* ヒープソートを行う */
void InitializeHeap( int n );	/* ヒープを構成する */
void DownHeap( int k, int r );	/* ヒープを正しく作り直す(ダウンヒープを行う) */

int main( )
{
	int i;			/* ループカウンタ */
	int n = NUM_DATA;	/* 要素数 */

	srand( (unsigned) time( NULL ) );	/* 実行毎に異なる疑似乱数を発生させる */

	SetData( );		/* データを作成 */

	puts( "ソ\ート前" );
	ShowData( );		/* 部分順序木構成前のデータを表示 */
	printf( "\n" );

	puts( "ヒープ構\成過程を表\示" );
	InitializeHeap( n );	/* ヒープを構成する */
	printf( "\n" );

	HeapMain( n );		/* ヒープソートを行う */
	puts( "ヒープソ\ート実行後" );
	ShowData( );		/* ソート後のデータを表示 */

	return 0;
}

/* データを作成 */
void SetData( )
{
	int i;		/* ループカウンタ */
	double rd;	/* [0,1)の実数乱数を格納する */

	for( i = 0; i < NUM_DATA; i++ ) {
		rd = rand() / ( RAND_MAX + 1.0 );	/* [0,1)の実数乱数を生成 */
		a[ i ] = (int) ( 100 + 1 ) * rd;	/* 0以上100以下の整数乱数を生成 */
	}
}

/* 各要素を表示 */
void ShowData( )
{
	int i;

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

/* ヒープソートを行う */
/* ヒープから最大値を取り出して，ヒープの大きさを1減らして，
DownHeapを用いてヒープを再構築する，という操作を繰り返す */
void HeapMain( int n )
{ 
	int i;			/* ループカウンタ */
	int k;			/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
	int r;			/* ヒープの要素数 */
	int tmp;		/* 一時格納変数 */

	i = n - 1;		/* 末尾の要素の前の要素 */
	while( i >= 0 ) {
		tmp = a[0]; 	/* 根の値(※最大値になってるはず)と最後の頂点(末尾の要素)を入れ替える */
		a[0] = a[i]; 	
		a[i] = tmp;
		i--;			/* 最後の頂点(末尾の要素)をヒープから除外する */
		k = 0; 			/* ダウンヒープを開始する頂点番号 */
		r = i;			/* 最後の頂点(末尾の要素)を除外した後のヒープ要素数 */
		DownHeap( k, r );	/* ダウンヒープ */
	}
}

/* ヒープを構成する */
/* 木を2つずつ組み合わせる操作を続けて，全体として1つの木にを作る(ヒープが完成) */
void InitializeHeap( int n )
{ 
	int i;	/* ループカウンタ */
	int k;	/* ダウンヒープを開始する頂点番号 */
	int r;	/* ヒープの要素数 */

	/* i = n / 2 - 1 初期値は親ノードの添え字を設定 */
	for( i = n / 2 - 1; i >= 0; i-- ) {
		k = i; 		/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
		r = n - 1;	/* 現在のヒープの要素数- 1 */
		DownHeap( k, r );	/* ダウンヒープ */
		ShowData( );		/* ダウンヒープの実行過程を表示 */
	} 
}

/* ヒープを正しく作り直す */
void DownHeap( int k, int r )
{ 
	int j;		/* ループカウンタ */
	int tmp;	/* 一時格納変数 */

	j = 2 * k + 1;	/* 最初は(とりあえず)左の子の添え字番号をjに代入 */
	while( j <= r ) {
		if( (j != r) && ( a[j+1] > a[j] ) )	/* j != r 左右両方の子供が存在するとき */
			/* j には左右の子のうち大きい方の添え字番号を代入 */
			j = j + 1;			/* a[j] とa[j + 1] を比較して大きい方をj とする */
			if( a[ k ] >= a[ j ] ) {	/* a[k] がa[j] 以上ならば終了 */
				break;			/* whileループを抜ける */
			}
			else {	/* そうでなければ，a[k]とa[j]の値を入れ替え */
				tmp = a[ k ]; 
				a[ k ] = a[ j ]; 
				a[ j ] = tmp;
				
				/* kとjの値を入れ替える */
				tmp = k; 		
				k = j; 			
				j = 2 * tmp + 1;	/* 左の子の添え字番号をjに代入 */
			}
	}
}