// The boolean operator "<=" must be defined for class C
// The assignment operator "=" must also be defined
#ifndef _heapTemplate_cpp
#define _heapTemplate_cpp
template<class C>
class heap{
public:
  heap(int n=1000);//constructor -- needs maximum size
  ~heap();//destructor
  bool isEmpty();
  C min();
  void insert(C x);
  C deleteMin();
  void printHeap();//prints it out in array form; assumes that "<<" is defined for class C
private:
  int currentSize, maxSize;
  C * A;
};

template <class C> // use ">" as a synonym for " not <="
bool operator > (C & c1, C & c2){return ! (c1 <= c2);}


//Implementation follows
template<class C> 
heap<C>::heap(int n){
  maxSize= n+1; 
  currentSize=0; 
  A = new C[maxSize];
}

template<class C> 
heap<C>::~heap(){delete[] A;}

template<class C> 
bool heap<C>::isEmpty(){return (currentSize == 0);}

template<class C> 
C heap<C>::min(){return A[1];}

template<class C> 
void heap<C>::insert(C x){
  currentSize += 1;
  int i = currentSize;
  A[0] = x; //This is added to avoid having to test to see if we've
 //reached the top of the heap (i.e., is i==1?). Since we've put x in
 //A[0],, the test A[i/2] > x is guaranteed to fail if i==1 (and i/2
 //is consequently equal to zero)
  while(A[i/2] > x){
    A[i] = A[i/2];
    i = i/2;
  }
  A[i] = x;
}

template<class C> 
C heap<C>::deleteMin(){
  C minVal = A[1];
  A[1] = A[currentSize];
  int i=1;
  for(;;){
    int min = i; // should be declared outside the loop
    if (2*i <= currentSize)   if (A[min] > A[2*i])   min = 2*i;
    if (2*i+1 <= currentSize) if (A[min] > A[2*i+1]) min = 2*i + 1;
    if (min == i) break;
    C tmp = A[i]; // should be declared outside the loop
    A[i]      = A[min];
    A[min]    = tmp;
    i = min;
  }
  currentSize -= 1;
  return minVal;
}

template<class C> 
void heap<C>::printHeap(){
  for (int i=1; i<= currentSize; i++) cout << A[i] << " ";
}
#endif