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

// Note: the user must supply the routine Min_Val,
// Which returns the minimum value of type Element_Type,
// Which is used as a sentinel.

static const Default_Max_Size = 10;

template <class Element_Type>
class Binary_Heap
{
  private:
    unsigned int Max_Size;	// Maximum number of elements.
    unsigned int Size;		// Current number of elements.
    Element_Type *Elements;	// The array.

  public:
    Binary_Heap( unsigned int Initial_Size = Default_Max_Size );
    ~Binary_Heap( );

    // Member functions.
    int Is_Empty( ) const;
    int Is_Full( ) const;
    const Element_Type & Find_Min( ) const;
    void Insert( const Element_Type & X );
    Element_Type Delete_Min( );
};




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


template <class Element_Type>
Binary_Heap<Element_Type>::
Binary_Heap( unsigned int Initial_Size )
{
    Size = 0;
    Max_Size = Initial_Size;
    Elements = new Element_Type [ Max_Size + 1 ];
    Elements[ 0 ]= Min_Val( );
}


template <class Element_Type>
Binary_Heap<Element_Type>::
~Binary_Heap(  )
{
    delete [] Elements;
}


////////////////////////////////////////////////////////////////////
//////////   Binary Heap --  utilities  ////////////////////////////
////////////////////////////////////////////////////////////////////
template <class Element_Type>
int
Binary_Heap<Element_Type>::
Is_Empty( ) const
{
   return Size == 0;
}


template <class Element_Type>
int
Binary_Heap<Element_Type>::
Is_Full( ) const
{
    return Size == Max_Size;
}


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

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

template <class Element_Type>
void
Binary_Heap<Element_Type>::
Insert( const Element_Type & X )
{
    unsigned int i;

    if( Is_Full( ) )
      std::cerr << "Error!  Binary_Heap is full!\n";
    else
    {
        i = ++Size;
        while( Elements[ i / 2 ] > X )
        {
            Elements[ i ] = Elements[ i / 2 ];
            i /= 2;
        }
        Elements[ i ] = X;
    }
}


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

template <class Element_Type>
Element_Type
Binary_Heap<Element_Type>::
Delete_Min( )
{
    unsigned int Child;
    Element_Type Min_Element, Last_Element;

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

    Min_Element = Elements[ 1 ];
    Last_Element = Elements[ Size-- ];

    int i;
    for( i = 1; i * 2 <= Size; i = Child )
    {
        // Find smaller child.
        Child = i * 2;
        if( Child != Size )
            if(  Elements[ Child + 1 ] < Elements[ Child ] )
                Child++;

        // Percolate one level.
        if( Last_Element > Elements[ Child ] )
            Elements[ i ] = Elements[ Child ];
        else
            break;
    }
    Elements[ i ] = Last_Element;

    return Min_Element;
}