// simple-minded heapsort which uses the STL priority queue
#include <iostream>
#include <queue>
using namespace std;

const int MAX = 20; // maximum size of array

void readArray(int a[], int &n);
void displayArray (int a[], int n);
void heapsort(int a[], int n);

int main()
{
    int a[MAX];
    int n;  // number of elements entered 
    cout << "Enter integers - terminate with control-z (control-d on unix) ";
    readArray(a,n);
    heapsort(a,n);
    cout << "Sorted Array " << endl;
    displayArray(a,n);
    system ("pause");
    return 0;
}
    
   
void readArray(int a[], int &n)
// precondition : none
// postcondition : reads in array until end-of-file or MAX elements have been
//                 read in.  Sets n to be the number of elements read in
//                 Note that n is passed by reference i.e. this function is
//                 changing the value of n. (don't redeclare n!!!)
{
   int num;
   for ( n = 0; n < MAX && cin >> num; n++)
   {
     a[n] = num;
   }
}

void displayArray(int a[], int n)
// precondition : none
// postcondition : displays the n elements of array a 
{
   for (int i = 0; i < n; i++)
     cout << a[i] << '\t';
   cout << endl;
}

void heapsort (int a[], int n)
// precondition : none
// postondition : a[0..n-1] is sorted in ascending order
// This is a simple-minded version using a priority queue of ints
{
   priority_queue <int> pq;
   for (int i = 0; i < n; i++)
      pq.push(a[i]);
   int i = n-1;
   while (!pq.empty())
   {
     a[i--] = pq.top();
     pq.pop();
   }
}