#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define U1 unsigned char
#define S1 char
#define	S4 int
#define DU double
#define VD void

#define MAX_HEAP_SIZE     (500000)   /* 最大ヒープサイズ */


/* TODO ヒープ配列のローカル変数化 */
S4 s4_g_heap[MAX_HEAP_SIZE];

S4 s4_d_setHeap(S4*);
VD vd_d_maxHeapify(S4*, S4, S4);
VD vd_d_buildMaxHeap(S4*, S4);
VD vd_d_outputHeap(S4*, S4);
S4 s4_d_calcRightIndex(S4);
S4 s4_d_calcLeftIndex(S4);
VD vd_d_swap(S4*, S4*);

S4 main()
{
	S4 s4_t_heapSize;

	s4_t_heapSize = s4_d_setHeap(s4_g_heap);
	vd_d_buildMaxHeap(s4_g_heap, s4_t_heapSize);
	vd_d_outputHeap(s4_g_heap, s4_t_heapSize);

	return((S4)0);
}

/* ユーザが入力した値をヒープに設定する */
/* 戻り値：ヒープサイズ */
S4 s4_d_setHeap(S4* s4_ap_heap)
{
	S4 s4_t_i;
	S4 s4_t_heapSize;

	s4_t_i = (S4)0;

	(VD)scanf("%d", &s4_t_heapSize);

	for (s4_t_i = (S4)0; s4_t_i < s4_t_heapSize; s4_t_i++)
	{
		(VD)scanf("%d", &s4_ap_heap[s4_t_i]);
	}

	return (s4_t_heapSize);
}

/* ヒープs4_ap_heapのインデックスs4_a_rootIndexの子ノードたちをmaxヒープ化 */
/* 子のキーが親より大きければ入れ替える、を再帰的に繰り返す */
VD vd_d_maxHeapify(S4* s4_ap_heap, S4 s4_a_rootIndex, S4 s4_a_heapSize)
{
	S4 s4_t_leftIndex;
	S4 s4_t_rightIndex;
	S4 s4_t_LargestIndex;	/* キーが最大のインデックス */

	s4_t_LargestIndex = s4_a_rootIndex;	/* 暫定で親のキーが最大とする */

	s4_t_leftIndex = s4_d_calcLeftIndex(s4_a_rootIndex);
	s4_t_rightIndex = s4_d_calcRightIndex(s4_a_rootIndex);

	/* 左の子が存在すれば、左の子と親のキーを比較 */
	if (s4_t_leftIndex < s4_a_heapSize)
	{
		if (s4_ap_heap[s4_t_leftIndex] > s4_ap_heap[s4_a_rootIndex])
		{
			s4_t_LargestIndex = s4_t_leftIndex;
		}
	}

	/* 右の子が存在すれば、右の子と親のキーを比較 */
	if (s4_t_rightIndex < s4_a_heapSize)
	{
		if (s4_ap_heap[s4_t_rightIndex] > s4_ap_heap[s4_t_LargestIndex])
		{
			s4_t_LargestIndex = s4_t_rightIndex;
		}
	}

	/* 親のキーが最大となるように入れ替え */
	if (s4_t_LargestIndex != s4_a_rootIndex)
	{
		vd_d_swap(&(s4_ap_heap[s4_t_LargestIndex]), &(s4_ap_heap[s4_a_rootIndex]));
		vd_d_maxHeapify(s4_ap_heap, s4_t_LargestIndex, s4_a_heapSize);
	}
}

/* ヒープをmaxヒープ化 */
VD vd_d_buildMaxHeap(S4* s4_ap_heap, S4 s4_a_heapSize)
{
	S4 s4_t_index;

	for (s4_t_index = s4_a_heapSize / (S4)2; s4_t_index >= (S4)0; s4_t_index--)
	{
		vd_d_maxHeapify(s4_ap_heap, s4_t_index, s4_a_heapSize);
	}
}

/* ヒープの値を出力する */
VD vd_d_outputHeap(S4* s4_ap_heap, S4 s4_a_heapSize)
{
	S4 s4_t_i;
	s4_t_i = (S4)0;

	for (s4_t_i = (S4)0; s4_t_i < s4_a_heapSize; s4_t_i++)
	{
		printf(" %d", s4_ap_heap[s4_t_i]);
	}
	printf("\n");
}

/* 引数s4_a_indexの右の子のインデックスを返す */
S4 s4_d_calcRightIndex(S4 s4_a_index)
{
	/* インデックスnの右の子は2n+2 */
	return((S4)2 * s4_a_index + (S4)2);
}

/* 引数s4_a_indexの左の子のインデックスを返す */
S4 s4_d_calcLeftIndex(S4 s4_a_index)
{
	/* インデックスnの左の子は2n+1 */
	return((S4)2 * s4_a_index + (S4)1);
}

/* 変数xと変数yの値を入れ替える */
VD vd_d_swap(S4* s4_ap_x, S4* s4_ap_y)
{
	S4 s4_t_tmp;
	s4_t_tmp = *(s4_ap_y);
	*(s4_ap_y) = *(s4_ap_x);
	*(s4_ap_x) = s4_t_tmp;
}
