// heapsort which uses heap class from Carrano
// We are becoming more object-oriented and generalised (and professional)
// Here KeyedItem is defined as just a string but see how easily it can be 
// extended to a student record or other structure
#include <iostream>
using namespace std;
#include "Heap.h"
const int MAX = 20;

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

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 (don't redeclare n!!!!)
//                 Note that no cin>> operator defined for KeyedItem so will
//                 need to read in a string and then use KeyedItem constructor
//                 to construct KeyedItem from string and assign to array

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
// Note will declare a heap and then insert all elements from
// array into heap.
// Then one by one delete (and save into array) the largest from the heap