/*---------------------------------------------------------------------------//

// heapsort.c       heap sort algorithm                               //

//                                                                           //

// Jun.07,2000       Version 0.1                         by : Lee Dong-Liang //

//---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------//

// Command Line Usage:                                                       //

//                                                                           //

//    sort  []                                   //

//                                                                           //

// the default NumberOfData=2000                                             //

//                                                                           //

// Data File Format                                                          //

// ...                                                                       //

// xxxxxxx = {IntegerData_i}                                                 //

// xxxxxxx = {IntegerData_i 1}                                               //

// ...                                                                       //

// i.e. one line contain only one data                                       //

//                                                                           //

// Restriction: the length of line data must < 128                           //

//                                                                           //

// If the number of data in DataFile is less than NumberOfData, the sorting  //

// will according to the number of data in DataFile.                         //

// But If the number of data in DataFile is more than NumberOfData, the      //

// sorting will according to NumberOfData.                                   //

//---------------------------------------------------------------------------*/



#include                   /* for printf,fopen,fclose,fgets,... */

#include                  /* for calloc,free, atoi */



int MAXIMUM_DATANUM=2000;           /* default Maximum data number = 2000 */



int ReadDataFromFile(char *filename,int *piData);

void heapsort(int *piData,int iDataNumber);



int main(int argc, char *argv[])

{

   int i,iDataNumber;

   int *piData;



   if(argc < 2 )                                   /* Check input command line */

   {                                               /* If error , exit */

      printf("Usage: %s  []\n",argv[0]);

      return 1;

   }



   if(argc > 2 )                                   /* Check input command line */

   {                                               /* If user spec. NumberOfData */

      MAXIMUM_DATANUM=atoi(argv[2]);

      if(MAXIMUM_DATANUM<=0) MAXIMUM_DATANUM=2000; /* If error , set to default */

   }



   piData=(int *) calloc(MAXIMUM_DATANUM 1,sizeof(int));   /* Allocate Memory */

                                                   /* Heap sort is 1-based */

   if(piData==NULL)                                /* Check Memory Status */

   {

      printf("Allocate Memory ERROR!!!\n");

      return 2;

   }



   iDataNumber=ReadDataFromFile(argv[1],piData 1); /* Read Source Data File */

                                                   /* Heap sort is 1-based */

   if( iDataNumber==0 )                            /* If error , exit */

   {

      printf("Error of reading file : \"%s\" !!!\n",argv[1]);

      printf("Please check : If the filename is correct ?\n");

      printf("               If the file format is correct ?\n");

      free(piData);

      return 3;

   }



   heapsort(piData,iDataNumber);                   /* Heap Sort */



   printf("  Heap  \n");                           /* Show Result */

   printf("========\n");

   for(i=0;i
      printf("}\n",piData[i 1]);                 /* Heap sort is 1-based */

   printf("========\n");



   free(piData);                                   /* Free Allocated Memory */



   return 0;

}



/*---------------------------------------------------------------------------//

// Data File Format                                                          //

// ...                                                                       //

// xxxxxxx = {IntegerData_i}                                                 //

// xxxxxxx = {IntegerData_i 1}                                               //

// ...                                                                       //

// i.e. one line contain only one data                                       //

//                                                                           //

// Restriction: the length of line data must < 128                           //

//---------------------------------------------------------------------------*/

int ReadDataFromFile(char *filename,int *piData)

{

   FILE *pFile;

   int i,iDataNumber=0;

   char strtemp[128];

   char *strNumber;



   pFile=fopen(filename,"r");                   /* Open File                */

   if( pFile == NULL ) return 0;



   for(;fgets(strtemp,128,pFile)!=NULL;)        /* Read a Line from File    */

   {

      for(i=0;i<128;i  )               /* Finding '='                       */

         if(strtemp[i]=='=' || strtemp[i]=='\0')break;

      if(strtemp[i]!='=')continue;     /* '=' Not Found ,continue next line */



      for(i  ;i<128;i  )               /* Finding '{'                       */

         if(strtemp[i]=='{' || strtemp[i]=='\0')break;

      if(strtemp[i]!='{')continue;     /* '{' Not Found ,continue next line */



      strNumber=&strtemp[i 1];         /* Data Start from Here!             */



      for(i  ;i<128;i  )               /* Finding '}'                       */

         if(strtemp[i]=='}' || strtemp[i]=='\0')break;

      if(strtemp[i]!='}')continue;     /* '{' Not Found ,continue next line */

      strtemp[i]='\0';



      piData[iDataNumber  ]=atoi(strNumber);    /* Convert Data             */

      if(iDataNumber>=MAXIMUM_DATANUM) break;   /* Test if Reach Buffer Len */

   }

   fclose(pFile);                               /* Close File               */

   return iDataNumber;

}

/*---------------------------------------------------------------------------//

// heapsort   algorithm                                                      //

//                                                                           //

//  procedure  sift-down(T[1..n],i)                                          //

//    {This procedure sifts node i down so as to re-establish the heap       //

//     property in T[1..n]. We suppose that T would be a heap if T[i]        //

//     were sufficiently large. We also suppose that 1 <= i <= n }           //

//    k = i                                                                  //

//    repeat                                                                 //

//       j = k                                                               //

//       { find the larger child of node j }                                 //

//       if 2j <= n and T[2j] > T[k]   then k = 2j                           //

//       if 2j <  n and T[2j 1] > T[k] then k = 2j 1                         //

//       exchange T[j] and T[k]                                              //

//       { if j=k, then the node has arrived at its final position }         //

//    until j=k                                                              //

//                                                                           //

//  procedure  make-heap(T[1..n])                                            //

//    {This procedure makes the array T[1..n] into a heap }                  //

//    for i =[n/2] down to 1 do sift-down(T,i)                               //

//                                                                           //

//  procedure  heapsort(T[1..n])                                             //

//    { T is an array to be sorted }                                         //

//    make-heap(T)                                                           //

//    for i = n downto 2 do                                                &n