/* Filename:  arrayutl.cpp

   Programmer:  Br. David Carlson

   Reference for HeapSort:  Data Structures with C++, by Ford and Topp,
   p 703.

   Date:  October 4, 1997

   Last Revised:  December 10, 2001

   This file (along with arrayutl.h) provides some useful routines for
   use with arrays: HeapSort, Print and FillArray.
*/

#include <iomanip>  // needed by setw
#include <cstdlib>  // needed by srand and rand functions
#include <ctime>    // needed by time function
#include "heap.h"


/* Given:  IntArray      Array of integers.
           Count  The number of integers in IntArray
   Task:   To print out the integers from IntArray.
   Return: Nothing.
*/
void Print(IntArrayType IntArray, int Count)
   {
   int k;

   for (k = 0; k < Count; k++)
      cout << setw(5) << IntArray[k];

   cout << endl;
   }


/* Given:  Nothing.
   Task:   To fill IntArray with random integers.
   Return: IntArray   Array of random integers.
*/
void FillArray(IntArrayType IntArray)
   {
   int k;

   srand(time(NULL));  // set an arbitrary starting point
   for (k = 0; k < Max; k++)
      IntArray[k] = (1000.0 * rand()) / RAND_MAX;
   }


/* Given:  IntArray  Array to be sorted.
           Count     The number of data items in IntArray.
   Task:   To sort IntArray into descending order using a heap sort.
   Return: IntArray  Sorted array.
*/
void HeapSort(IntArrayType IntArray, int Count)
   {
   int Smallest, k;
   HeapClass H(IntArray, Count);  // constructor makes IntArray a heap

   for (k = Count - 1; k >= 1; k--)
      {
      // Remove smallest item and place at index k
      Smallest = H.Delete();
      IntArray[k] = Smallest;
      }
   // At this point IntArray[0] contains the largest item by default
   }