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

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

/* グローバル変数 */
int a[NUM_DATA] = { 54, 41, 18, 31, 70, 17, 60, 89, 36, 98, };

/* プロトタイプ宣言 */
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_Fix(int a[], int N)
{
	int i;		/* ループカウンタ */
	double rd;	/* [0,1)の実数乱数を格納する */

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

	for (i = 0; i < N; i++) {
		printf("%d, ", a[i]);
	}
	printf("\n");
}
void DownHeap_Fix(int a[],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に代入 */
		}
	}
}
void InitializeHeap_Fix(int a[],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_Fix(a,k, r);	/* ダウンヒープ */
		ShowData_Fix(a,n);		/* ダウンヒープの実行過程を表示 */
	}
}
void HeapMain_Fix(int a[], int n)
{
	int i;			/* ループカウンタ */
	int k;			/* ダウンヒープを開始する頂点番号(ヒープの条件がくずれている位置) */
	int r;			/* ヒープの要素数 */
	int tmp;		/* 一時格納変数 */

	if (n <= 0) return;

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

}

void StartA(int Data[], int N){
	InitializeHeap_Fix(Data, N);
	HeapMain_Fix(Data, N);
	puts("AfterA:");
	ShowData_Fix(Data, N);
}

void StartB(int N){
	InitializeHeap(N);
	HeapMain(N);
	puts("AfterB:");
	ShowData();
}
int main(){

	int Data[NUM_DATA] = { 54, 41, 18, 31, 70, 17, 60, 89, 36, 98, };

	puts("BeforeA:");
	ShowData_Fix(Data,NUM_DATA);
	puts("");
	StartA(Data, NUM_DATA);
	
	puts("\n");

	puts("BeforeB:");
	ShowData();
	puts("");
	StartB(NUM_DATA);

	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に代入 */
		}
	}
}