#ifndef BINARY_HEAP_H#define BINARY_HEAP_H#include "dsexceptions.h"#include <vector>using namespace std;// BinaryHeap class//// CONSTRUCTION: with an optional capacity (that defaults to 100)//// ******************PUBLIC OPERATIONS*********************// void insert( x )       --> Insert x// deleteMin( minItem )   --> Remove (and optionally return) smallest item// Comparable findMin( )  --> Return smallest item// bool isEmpty( )        --> Return true if empty; else false// void makeEmpty( )      --> Remove all items// ******************ERRORS********************************// Throws UnderflowException as warrantedtemplate <typename Comparable>class BinaryHeap{  public:    explicit BinaryHeap( int capacity = 100 )      : array( capacity + 1 ), currentSize( 0 )    {    }    explicit BinaryHeap( const vector<Comparable> & items )      : array( items.size( ) + 10 ), currentSize( items.size( ) )    {        for( int i = 0; i < items.size( ); i++ )            array[ i + 1 ] = items[ i ];        buildHeap( );    }    bool isEmpty( ) const      { return currentSize == 0; }    /**     * Find the smallest item in the priority queue.     * Return the smallest item, or throw Underflow if empty.     */    const Comparable & findMin( ) const    {        if( isEmpty( ) )            throw UnderflowException( );        return array[ 1 ];    }    /**     * Insert item x, allowing duplicates.     */    void insert( const Comparable & x )    {        if( currentSize == array.size( ) - 1 )            array.resize( array.size( ) * 2 );            // Percolate up        int hole = ++currentSize;        for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )            array[ hole ] = array[ hole / 2 ];        array[ hole ] = x;    }    /**     * Remove the minimum item.     * Throws UnderflowException if empty.     */    void deleteMin( )    {        if( isEmpty( ) )            throw UnderflowException( );        array[ 1 ] = array[ currentSize-- ];        percolateDown( 1 );    }    /**     * Remove the minimum item and place it in minItem.     * Throws Underflow if empty.     */    void deleteMin( Comparable & minItem )    {        if( isEmpty( ) )            throw UnderflowException( );        minItem = array[ 1 ];        array[ 1 ] = array[ currentSize-- ];        percolateDown( 1 );    }    void makeEmpty( )      { currentSize = 0; }  private:    int                currentSize;  // Number of elements in heap    vector<Comparable> array;        // The heap array    /**     * Establish heap order property from an arbitrary     * arrangement of items. Runs in linear time.     */    void buildHeap( )    {        for( int i = currentSize / 2; i > 0; i-- )            percolateDown( i );    }    /**     * Internal method to percolate down in the heap.     * hole is the index at which the percolate begins.     */    void percolateDown( int hole )    {        int child;        Comparable tmp = array[ hole ];        for( ; hole * 2 <= currentSize; hole = child )        {            child = hole * 2;            if( child != currentSize && array[ child + 1 ] < array[ child ] )                child++;            if( array[ child ] < tmp )                array[ hole ] = array[ child ];            else                break;        }        array[ hole ] = tmp;    }};#endif

#include <iostream>#include "BinaryHeap.h"using namespace std;    // Test programint main( ){    int numItems = 99999;    BinaryHeap<int> h;    int i = 37;    int x;    cout << "Begin test... " << endl;    for( i = 37; i != 0; i = ( i + 37 ) % numItems )        h.insert( i );    for( i = 1; i < numItems; i++ )    {        h.deleteMin( x );        if( x != i )            cout << "Oops! " << i << endl;    }    for( i = 37; i != 0; i = ( i + 37 ) % numItems )        h.insert( i );    h.insert( 0 );    cout << "End test... no other output is good" << endl;    return 0;}