//
// Heap class implementation
// (array based)
//

#ifndef __HEAP
#define __HEAP

// Node class
template <class T>
class __HeapNode {
 public:
  int prio;
  T value;
};

// Heap Class
template <class T>
class Heap {
  int Size, Last;
  __HeapNode<T> *A;
 
 public:

  Heap ();
  Heap (int Size);
  ~Heap () { delete []A; }

  virtual bool isEmpty () const { return Size > 0 ? false : true; }
  virtual bool Insert (int, T&); 
  virtual bool Delete (T&); 

  friend ostream& operator << <> (ostream& out, Heap<T>&);

 private:
  bool rebuildHeap (int, int); 

};

template <class T>
Heap<T>::Heap ()
{
  this->Last = -1;
  this->Size = 100;
  A = new __HeapNode<T>[100];
}

template <class T>
Heap<T>::Heap (int Size)
{
  this->Last = -1;
  this->Size = Size;
  A = new __HeapNode<T>[Size];
}

template <class T>
bool Heap<T>::Insert (int prio, T& value)
{
  if (this->Last < Size)
    {
      int i = ++this->Last, j = 0;
      // Find the position of insertion
      for (j = (this->Last-1)/2; i > 0; i = j, j = (j-1)/2)
	// Move elements down in tree as long as new prio is higher
	if (A[j].prio < prio)
	  {
	    A[i].prio = A[j].prio; 
	    A[i].value = A[j].value;
	  }
	else
	  break;
      // Insert into the correct place
      A[i].prio = prio;
      A[i].value = value;	 
      return true;
    }
  return false;
}


template <class T>
bool Heap<T>::Delete (T& value)
{
  if (Last > -1)
    {
      int i = 0;
      value = A[0].value;
      // Find position to move the last element
      while (i < Last)
	{
	  int left = 2*i+1, right = 2*i+2, move = Last;
	  // Find the maximum of i and its children and save
	  if ((left <= Last) && (A[left].prio > A[move].prio))
	    move = left;
	  if ((right <= Last) && (A[right].prio > A[move].prio))
	    move = right;
	  // Already the right position
	  if (move == Last)
	    break;
	  // Move up the maximum
	  A[i].prio = A[move].prio;
	  A[i].value = A[move].value;
	  i = move;
	}
      // Insert in the right place
      A[i].prio = A[Last].prio;
      A[i].value = A[Last].value;
      this->Last--;
      return true;
    }
  return false;
}

template <class T>
ostream& operator << (ostream& out, Heap<T>& h)
{
  for (int i = 0; i <= h.Last; i++)
    out << h.A[i].prio << ":" << h.A[i].value << " ";
  out << endl;
  return out;
}


template <class T>
bool Heap<T>::rebuildHeap (int Root, int Last)
{
  if (Last > -1)
    {
      int i = Root;
      int prio = A[Root].prio;
      T value = A[Root].value;

      // Find position to move the last element
      while (i < Last)
	{
	  int left = 2*i+1, right = 2*i+2, move = i;
	  // Find the maximum of i and its children and save
	  if ((left <= Last) && (A[left].prio > A[move].prio))
	    move = left;
	  if ((right <= Last) && (A[right].prio > A[move].prio))
	    move = right;
	  // Already the right position
	  if (move == Last)
	    break;
	  // Move up the maximum
	  A[i].prio = A[move].prio;
	  A[i].value = A[move].value;
	  i = move;
	}
      A[i].prio = prio;
      A[i].value = value;
      return true;
    }
  return false;
}

#endif // __HEAP