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

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

void SetDataB(int a[],int N)
{
	int i;		/* ループカウンタ */

	for (i = 0; i<N; i++) {
		a[i] = N-i-1;	/* 0以上100以下の整数乱数を生成 */
	}
}
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);
}

int main(){

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

	SetDataB(Data, NUM_DATA);

	puts("BeforeA:");
	ShowData_Fix(Data,NUM_DATA);
	puts("");
	StartA(Data+N,NUM_DATA-N*2);

	puts("Result");
	ShowData_Fix(Data, NUM_DATA);

	return 0;
}