/*  CSC 155 Assignment "hsort".  Due Monday 3/7/05.

    Please implement the following header for the heap data structure.  Note
    that the type of heap you'll be implementing should have the largest
    element at the root, because we will want to use the heap to sort
    an array.


A.  Implement the insert and deletemin functions as described in class
 
B.  One can use the basic characteristics of a heap to implement a sorting
    algorithm as follows:

 1.  Given array A, insert the elements one by one into the heap array.
    Each insert takes lg(n) time and there are n elements, so this operation
    is n*lg(n).  

 2.  Now, reconstruct the A array by deleting the maximum element from the
    heap one by one.  This will again take n(log n) time.

 
C. On the class homepage you'll find a program "quicksort.cpp" that 
   times the real-time performance of the quicksort routine
   (it's pretty darn fast!)  Using that program as a template, compare
   your algorithm against quicksort for arrays of 2, 4, 6, and 8 million
   integers.  Be sure to use the -O2 option of g++ to optimize your code.
   Do the empirical results confirm your theory as to the behavior of
   the algorithms?  Don't just look at the raw numbers, look at the
   GROWTH RATE.  Why is it that one still outperforms another?

Optional challenge.  The above algorithm uses an extra array and
    copies values back and forth.  Can you devise an algorithm that
    uses only one array?  Hint: when deleting the root element,
    instead of throwing it away, SWAP it with the last element in the
    heap.

*/


class heap
{
private:
  int HEAPMAX;     
  int* H;
  int last; // last valid index;  
public:   
  heap() ;
  ~heap();
  // These functions should return the index of the appropriate node
  int parent(int i);
  int lchild(int i);
  int rchild(int i);

  void insert(int x);  // insert new element x into heap
  void deleteMax();    // delete the maximum value, i.e., the root

  // Sort an array using the heap:
  void heapsort(int *A, int sizeofA);
};