// #include "heap.h"
#include <iostream>


template<class Comparable>
BinaryHeap<Comparable>::BinaryHeap(int capacity):
  a(vector<Comparable>(capacity)),currentSize(0) {}


// The "insert" methods assumes no possibility of overflow
// Otherwise it is taken from p 216 of the text

template <class Comparable>
void BinaryHeap<Comparable>::insert(const Comparable &x)   {
  int hole=++currentSize;
  for (; hole>1 && x<a[hole/2]; hole/=2) 
    a[hole]=a[hole/2];               
  a[hole]=x;                                               }


// The "deleteMin" method assumes that there can be no underflow
// Otherwise it is taken from the text.

template <class Comparable>
void BinaryHeap<Comparable>::deleteMin(Comparable &minItem){
  minItem=a[1];
  a[1]=a[currentSize--];
  percolateDown(1);                                        }


// The "percolateDown" method is taken from the text.

template <class Comparable>
void BinaryHeap<Comparable>::percolateDown(int hole)       {
int child;
Comparable tmp=a[hole];
for (; hole * 2 <= currentSize; hole=child)              {
  child=hole*2;
  if (child!=currentSize && a[child+1]<a[child])
    child++;
  if (a[child]< tmp)
    a[hole]=a[child];	                                       
  else
    break;                                               }
a[hole]=tmp;                                               }


// The "buildHeap" method is taken from the text.

template <class Comparable>
void BinaryHeap<Comparable>::buildHeap()                               {
  for (int i=currentSize/2 ; i>0; i--)
    percolateDown(i);                                      }