/*  Polymorphic Heaps */

/**********

To use this structure (for example, with ints):

heap<int> H(1000);  // must specify max size of heap
comparator<int> *cm = new comparator<int>();
H.insert(3,cm);  // inserts new element from the heap
int x = H.deleteRoot(cm); // deletes and returns top of heap
int length = H.last;     // last variable also indicates size of heap
bool memberof = H.inheap(4,cm);  // determines if heap contains 4

**********/

using namespace std;

template <typename ST>
class comparator
{
 public:
  bool le(ST a, ST b);   // less than
  bool eq(ST a, ST b);   // equal to
};

bool comparator<int>::le(int a, int b)
{  return a<b; }
bool comparator<int>::eq(int a, int b)
{  return a==b; }
bool comparator<double>::le(double a, double b)
{  return a<b; }
bool comparator<double>::eq(double a, double b)
{  return a==b; }



template <typename ST>
class heap
{
private:
  int HEAPMAX;
  ST* H;
public:   
  int last; // last valid index, also size of heap
  heap(int hs) 
  { last = 0; 
    HEAPMAX = hs;
    H = new ST[HEAPMAX];
  }
  ~heap() { delete(H); }   // must delete cells independently

  int parent(int i) { return i/2; }
  int lchild(int i) { return (i*2); }
  int rchild(int i) { return (i*2)+1; }

  void insert(ST x, comparator<ST> *cm) // insert x into heap
  {
    ST temp;
    H[++last] = x; // first put x at end of heap;
    int i = last;
    // propagate upwards  
    while (i>1 && ( cm->le(H[parent(i)],H[i]) ))
      {
	temp = H[i];
	H[i] = H[parent(i)];
	H[parent(i)] = temp;
	i = parent(i);
      }
  } // insert

  ST deleteRoot(comparator<ST> *cm)  // delete the root element, return it
  { 
    // put last value at root, then propagate downwards
    ST temp, root;   // for swap
    if (last<1) throw "heap is empty";
    root = H[1];
    H[1] = H[last];
    H[last--] = root;
    int i = 1;
    while (i<last && ((lchild(i)<=last && cm->le(H[i],H[lchild(i)]))
		      || (rchild(i)<=last && cm->le(H[i],H[rchild(i)]))))
      {
	// find the larger of the two childeren, and swap:
        int s;
	if ((rchild(i)>last) || (cm->le(H[rchild(i)],H[lchild(i)]))) 
	  s = lchild(i);   else s = rchild(i);
	// swap 
	temp = H[i];
	H[i] = H[s];
	H[s] = temp;
	i = s;  
      }
    return root;
  } // deleteMax

  bool inheap(ST x,comparator<ST> *cm) // search heap for x
  {
    // do straight forward array search
    bool ax = false;
    int i;
    for(i=1;i<=last && !ax;i++) ax = (cm->eq(x,H[i]));
    return ax;
  }

};  // heap