// heapsort which uses heap class from Carrano
#include <iostream>
using namespace std;
#include "Heap.h"

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

const int MAX = 20;

int main()
{
    KeyedItem a[MAX];
    int n;  // number of elements entered 
    cout << "Enter strings - 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(KeyedItem 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
{
   string s;
   for ( n = 0; n < MAX && cin >> s; n++)
   {
     a[n] = KeyedItem(s);
   }
}

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

void heapsort (KeyedItem a[], int n)
// precondition : none
// postondition : a[0..n-1] is sorted in ascending order
// This is a version using Carrano's heap class directly

{
     Heap h;
     for (int i = 0; i < n; i++)
        h.heapInsert(a[i]);

     int last = n-1;
     while (!h.heapIsEmpty())
     {
         h.heapDelete(a[last]);
         last--;
     }  
}