#ifndef _MINHEAP_CPP
#define _MINHEAP_CPP

#include "MinHeap.h"
#include "cassert"

using namespace std;

template <class Object, class Compare>
MinHeap<Object,Compare>::MinHeap()
{
  max_size = 1;
  array = new Object[2];
  curr_size = 0;
}

// Constructor - initializes heap to size 
template <class Object, class Compare>
MinHeap<Object,Compare>::MinHeap(int size)
{
  max_size = size;
  array = new Object[size+1];
  curr_size = 0;
}

template <class Object, class Compare>
MinHeap<Object,Compare>::~MinHeap() 
{
  delete [] array;
}

template <class Object, class Compare>
void MinHeap<Object,Compare>::makeEmpty()
{
  curr_size = 0;
}

template <class Object, class Compare>
bool MinHeap<Object,Compare>::isEmpty() const
{
  return curr_size == 0;
}

template <class Object, class Compare>
const Object & MinHeap<Object,Compare>::findMin() const
{
  assert(!isEmpty());
  return array[1];
}

template <class Object, class Compare>
void MinHeap<Object,Compare>::insert( const Object & x) 
{
  if(curr_size == max_size)
    resizeHeap();
  curr_size += 1;
  percolateUp(x, curr_size );
}

template <class Object, class Compare>
void MinHeap<Object,Compare>::deleteMin() 
{
  assert(!isEmpty());
  removeMin();
}

template <class Object, class Compare>
void MinHeap<Object,Compare>::deleteMin(Object & minItem ) 
{
  assert(!isEmpty());
  minItem = array[1];
  removeMin();
}


template <class Object, class Compare>
void MinHeap<Object,Compare>::percolateUp(const Object & x, int hole ) 
{
  for( ; hole > 1 && comp(x,array[ hole/2 ]); hole = hole/2 )
    array[ hole ] = array[ hole/2 ];
  array[ hole ] = x;
}

template <class Object, class Compare>
void MinHeap<Object,Compare>::percolateDown( int hole ) 
{
  int child;
  Object temp = array[hole];

  for( ; hole * 2 <= curr_size; hole = child )
    {
      child = hole * 2;
      if(child != curr_size && comp( array[ child + 1 ], array[ child ] ) )
	child++;
      if( comp( array[ child ], temp ) )
	array[ hole ] = array[ child ];
      else
	break;
    }
  array[ hole ] = temp;
}

template <class Object, class Compare>
void MinHeap<Object,Compare>::removeMin() 
{
  array[1] = array[ curr_size ];
  // decrease the current size
  curr_size -= 1;

  // re-heap the array
  percolateDown(1);
}


template <class Object, class Compare>
void MinHeap<Object,Compare>::resizeHeap() 
{
  // You must finish the code for this function

}

template <class Object, class Compare>
void MinHeap<Object,Compare>::reHeap() 
{
  // You must finish the code for this function
}

template <class Object, class Compare>
void MinHeap<Object,Compare>::buildHeap(Object * x, int size) 
{
  // You must finish the code for this function
}

#endif