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

using namespace std;

void sort(vector<int> &vec);
void reheap(vector<int> &vec, int i, int n);

template <class T>
inline void Swap(T &a, T &b)
{
   T temp = a;
   a = b;
   b = temp;
}

bool check(const vector<int> &list)
{
    for(int a = 0; a < list.size() - 1; a++)
        if(list[a] > list[a + 1])
        {
            cout << "Error: " << list[a] << " is greater than " << list[a + 1];
            cout << "\n\tError at: " << a << endl;
            return false;
        }
    return true;
}  

int main()
{
      ifstream fileIn("in1100.txt");

      clock_t t1, t2;
      vector<int> vec;
      int num;
      // heapsort doesn't use array position 0, so
      // if we use a negative number, the 'check'
      // function will still work 
      vec.push_back(-1);

      while(fileIn >> num) vec.push_back(num);

      t1 = clock();
      sort(vec);
      t2 = clock();

      if(check(vec))
        cout << "Checked out OKAY.\n\n";
      else
        cout << "There were errors...\n\n";

      // subtract 1 from size because of the -1 we have to push back
      cout << "Total time for " << (vec.size() - 1) << " elements: " << (t2 - t1) / (float)CLOCKS_PER_SEC << endl;

      system("PAUSE");
      return 0;
}

void sort(vector<int> &vec)
{
   int i, n = vec.size() - 1;

   for(i = n/2; i >= 1; i--)
       reheap(vec, i, n);

   while(n > 1)
   {
      Swap(vec[1],vec[n]);
      --n;
      reheap(vec, 1, n);
   }
}

void reheap(vector<int> &vec, int i, int n)
{
   int x = vec[i];

   int parent = i;
   i *= 2;
   while(i <= n)
   {
     if(i < n && vec[i] < vec[i+1])
        i++;
     if(vec[i] <= x) break;

     vec[parent] = vec[i];
     parent = i;
     i *= 2;
   }

   vec[parent] = x;
}