/* FILE: heapSort.cpp   last change: 16-Mar-2001   author: Romeo Rizzi
 * This program reads a file of n unsorted integers and sorts them.
 * The integers are first put into a static array,
 * whose dimension is at most MAX_INTEGERS.
 * Then, the array is made to satisfy the heap property.
 * Finally, the biggest integer is iteratively extracted from the
 * heap and put in the right place.
 */

#include <fstream.h>
#include <iostream.h>

const long int  MAX_INTEGERS = 1000;

void Maximize(double*, const long int&, const long int&);
void MakeHeap(double*, const long int&);
void MaxSort(double*, const long int&);

main(int argc, char** argv) {
  if (argc < 2 || argc > 3) {
     cerr << "syntax:" << endl
          << " > heapsort <file1>" << endl
          << "or" << endl
          << " > heapsort <file1> <file2>" << endl
          << "where, <file1> = input file of unordered numbers" << endl
          << "and, <file2> = output sorted file" << endl;
     exit(1);
  }

  ifstream  in;
  in.open(argv[1]);
  if (!in.good()) {
     cerr << "err: file " << argv[1] << " does not exist" << endl;
     exit(1);
  }

  double A[MAX_INTEGERS+1];
  long int n = 0;
  do {
     in >> A[++n];
     if (n > MAX_INTEGERS) {
        cerr << "err: file " << argv[1] << " contains more than "
             << MAX_INTEGERS << " integers." << endl;
        exit(1);
     }
  } while (!in.eof());
  in.close();

   MakeHeap(A, n);
   MaxSort(A, n);

  if (argc == 2)  for(long int i = 1; i <= n; i++)  cout << A[i] << endl;
  else {
     ofstream  out;
     out.open(argv[2]);
     if (!out.good()) {
        cerr << "err: could not open file " << argv[2] << endl;
        exit(1);
     }
     for(long int i = 1; i <= n; i++)  out << A[i] << endl;
     out.close();
  }
}

inline void Maximize (double* A, const long int& i, const long int& j)  {
   long int root = i;    bool done = false;
   double value = A [i];
   while ( 2*root <= j  &&  ! done )  {
      long int posMax =  2 * root;
      if (posMax < j)
         if (A [posMax+1] > A [posMax])  posMax++;
      if (A [posMax] > value)  {
         A [ root ] = A [ posMax ];
         root = posMax;
      }
      else  done = true;
   }
   A [root] = value;
}


inline void MakeHeap (double* A, const long int& n) { // enforces the heap property
   for(long int i = (n / 2);  i >= 1; i--)  Maximize(A, i, n);
}


void MaxSort (double* A, const long int& n) { // sorting from heap
  long int i = n;
  while (i > 1)  {
     double swap = A [1];
     A [1] = A [i];
     A [i] = swap;
     i = i-1;
     Maximize (A, 1, i);
  }
}