////////////////////////////////////////////////////////////////////
//////////   Binary Heap class declaration    //////////////////////
////////////////////////////////////////////////////////////////////

#include <vector>

template <class Element_Type>
class Binary_Heap
{
  private:
    std::vector<Element_Type> Elements;

  public:
    Binary_Heap( );
    Binary_Heap( Element_Type* values, int n );
    ~Binary_Heap( );

    // Member functions.
    bool Is_Empty( ) const;
    int NumElements() const { return Elements.size(); }
    const Element_Type & Find_Min( ) const;
    void Insert( const Element_Type & X );
    Element_Type Delete_Min( );

  private:
    void Percolate_Down( int i );
};




////////////////////////////////////////////////////////////////////
//////////   Binary Heap constructor and destructor  ///////////////
////////////////////////////////////////////////////////////////////

//  Default constructor now does nothing.
template <class Element_Type>
Binary_Heap<Element_Type>::
Binary_Heap( )
{
}


template <class Element_Type>
Binary_Heap<Element_Type>::
Binary_Heap( Element_Type* values, int n )
{
  Elements.insert(Elements.begin(), &values[0], &values[n] );
  for ( int i=n/2-1; i>=0; i-- ) Percolate_Down(i);
}


template <class Element_Type>
Binary_Heap<Element_Type>::
~Binary_Heap(  )
{
}


////////////////////////////////////////////////////////////////////
//////////   Binary Heap --  utilities  ////////////////////////////
////////////////////////////////////////////////////////////////////
template <class Element_Type>
bool
Binary_Heap<Element_Type>::
Is_Empty( ) const
{
   return Elements.size() == 0;
}


template <class Element_Type>
const Element_Type &
Binary_Heap<Element_Type>::
Find_Min( ) const
{
    return Elements[0];   // assuming it isn't empty
}

////////////////////////////////////////////////////////////////////
//////////   Binary Heap --  insert   //////////////////////////////
////////////////////////////////////////////////////////////////////

template <class Element_Type>
void
Binary_Heap<Element_Type>::
Insert( const Element_Type & X )
{
    Elements.push_back(X);
    int i = Elements.size()-1;  // current location
    int p = (i-1)/2;          // parent
    while( i > 0 && Elements[p] > X )
    {
      Elements[ i ] = Elements[ p ];
      i = p;   p = (i-1)/2;
    }
    Elements[i] = X;
}


////////////////////////////////////////////////////////////////////
//////////   Binary Heap --  delete min   //////////////////////////
////////////////////////////////////////////////////////////////////

template <class Element_Type>
Element_Type
Binary_Heap<Element_Type>::
Delete_Min( )
{
    if( Is_Empty( ) )
    {
        std::cerr << "Priority queue is empty\n";
        return Elements[ 0 ];	// If error is not fatal.
    }

    Element_Type Min_Element = Elements[0];
    Elements[0] = Elements[ Elements.size()-1 ];
    Elements.pop_back();
    Percolate_Down( 0 );
    return Min_Element;
}

template <class Element_Type>
void
Binary_Heap<Element_Type>::
Percolate_Down( int i )
{
    Element_Type to_place = Elements[i];
    int size = Elements.size();
    int child=2*i+1;  // left child location
    while ( child < size )
    {
        // Find smaller child.
	int rchild = child+1;
        if( rchild != size && Elements[ rchild ] < Elements[ child ] )
	    child = rchild;

        // Percolate one level.
        if( to_place > Elements[ child ] )
	  {
	    Elements[ i ] = Elements[ child ];
	    i = child;
	    child = 2*i+1;
	  }
        else
            break;
    }
    Elements[ i ] = to_place;
}