#include<stdio.h>
#include<stdlib.h>
//lab9
//h306119山本恭大
#define N 100000

int deletemin(int *A,int *n);//ヒープ内の一番小さい数をけす
void downmin(int i,int *A,int n);//木をヒープの順に並び変える
void swap(int i,int j,int *A);//配列A[i]とA[j]を入れ替える
void insert(int x,int *A,int *n);//木に新しい要素を入れる
void upmin(int i,int *A,int n);//ヒープの数を比較し、親の方が大きかったとき入れ替える

int main(int argc,char *argv[])
{
	FILE *fp;
 	fp = fopen("rand1000.dat","r");//テキストを開く
	int A[N];
	int a,b,n=0,i,m,temp,j,k;
	fscanf(fp,"%d",&a);//要素の数を決める
	for(i=0;i<a;i++){//要素の数だけまわす
		fscanf(fp,"%d",&b);//新しい要素に入れる数
		insert(b,A,&n);//新しい要素を作る
	}
	//========木構造の表示=========================================
	temp=1;
		for(j=1;j<=n;j++){
			if(temp==j){
				if(j!=1) printf("\n");
			temp*=2;
			}
			printf(" %d",A[j-1]);
		}
		//=============================================================
		k=n;
	while(n>0){
	A[k]=deletemin(A,&n);//最大値を配列へ代入
	k--;
 	}
	printf("\nwood end\n\n\n\n");
	for(i=0;i<a;i++) printf("%d ",A[i]);//整列された数字を表示する
	fclose(fp);
}

//ヒープ内の一番大きい数をけす
	int deletemin(int *A,int *n)
	{
		int min,n1;
		n1= *n;
		if(n1<1){//要素の数が0より小さいとき
			printf("\n%d\n",n1);
			printf("Error: Heap is empty.\n");
			return -1;
		}
		min=A[0];A[0]=A[n1-1];//最大値を消す
		if(n1>1) downmin(0,A,n1-1);
		*n=n1-1;//全体の要素数をへらす
		return min;
	}

//木をヒープの順に並び変える
	void downmin(int i,int *A,int n)
	{
		int j;
		if(i<0 || i>=n)
		{
			printf("Illegal element i=%d for n=%d\n",i,n);exit(1);
		}
		j=2*i+1;
		if(j>=n) return;
 		if(j+1<n && A[j]<A[j+1]) j=j+1;

		if(A[j]>A[i])
		{
			swap(i,j,A);//入れ替え
			downmin(j,A,n);//並び替え
		}
		return ;
	}

	void swap(int i,int j,int *A)
	{
		int temp;
		temp=A[i];A[i]=A[j];A[j]=temp;
		return;
	}
//木に新しい要素を入れる
void insert(int x,int *A,int *n)
{ 
	int n1;
	n1=*n;
	if(n1>=N)
	{
		printf("Error: Heap A is full.\n");
		exit(1);
	}
	A[n1]=x;
	upmin(n1,A,n1+1);
	*n=n1+1;
	return;
}  
 
//ヒープの数を比較し、親の方が小さかったとき入れ替える
void upmin(int i,int *A,int n)
{ 
	int j;
	if(i<0 || i>=n)
	{
		printf("Illegal element i=%d for n=%d\n",i,n);exit(1);
	}
	if(i==0) return;
	j=(i-1)/2;
	if(A[j]<A[i])
	{
		swap(i,j,A);//入れ替え
		upmin(j,A,n);//並び替え
	}
	return;
}