#include<stdio.h>
#include<stdlib.h>
#include<time.h>

//ファイルからデータを読み込んで配列に格納する
int* inputData(char *fileName,int *data,int length){
  FILE *fo;
  int i;
  char str[256];

  if((fo=fopen(fileName,"r"))==NULL){//リードモードでファイルを開く
    printf("Can't Open Input File.\n");
    exit(1);
  }

  i=0;
  while(fgets(str,256,fo)!=NULL){//ファイルからデータを読み込む
    data[i]=atoi(str);
    i++;
  }
  return data;
}

void heap(int c,int size,int *data){
  int child,p;
  int tmp;

  child=data[c];
  while(1){
    p=(c-1)/2;// 親のインデックスを計算
    if(c<0) break;
    if(c!=0){
      if (data[c]>data[c-1]) {
	c=c-1;
      }
    }
    if (data[p]<=data[c]) break;	// 親の方が小さい場合はbreak
    
    tmp=data[p];
    data[p]=data[c];
    data[c]=tmp;
    c=p;//親ノードを新たな子ノードにする
  }
}

int heap_sort(int c,int size,int *data){
  int tmp,i,j;
  
  //最初のヒープを作る
  for(i=size-1;i>=0;i--){
    heap(i,size,data);
  }
  //根のデータと最後のデータを入れかえてソートする。
  for(i=size-1;i>=0;i--){
    tmp=data[0];
    data[0]=data[i];
    data[i]=tmp;
    for(j=i;j>=0;j--){
      heap(j-1,j,data);
    }
  }
}

void outputData(int *data,int length){
  int i;

  //結果を標準出力
  printf("\n*****Result*****\n");
  for(i=length-1;i>=0;i--){
    printf("%d ",data[i]);
  }
  printf("\n");
}

int main(int argc,char *argv[]){
  int length,i;
  int *data;
  
  if(argc!=3){
    printf("Please Enter Length and File Name\n");
    exit(1);
  }
  if(!isdigit(*argv[1])){
    printf("Length is Integer!!!\n");
    exit(1);
  }
  length=atoi(argv[1]);
   
  //int型配列を用意する
  data=(int*)malloc(sizeof(int)*length);

  data=inputData(argv[2],data,length);
   
  printf("***DATA***\n");
  for(i=0;i<length;i++){
    printf("%d ",data[i]);
  }
  printf("\n");

  heap_sort(length-1,length,data);
  outputData(data,length);
  free(data);
  return(0);
}