#ifndef QUEUE_CPP_ #define QUEUE_CPP_ #include "StartConv.h" template priority_queue::priority_queue( ) : theItems( 1 ), lessThan( Compare( ) ) { } template int priority_queue::size( ) const { return theItems.size( ) - 1; } template bool priority_queue::empty( ) const { return size( ) == 0; } template const Object & priority_queue::top( ) const { if( empty( ) ) throw UnderflowException( "Cannot top an empty priority queue" ); return theItems[ 1 ]; } template void priority_queue::push( const Object & x ) { theItems.push_back( x ); theItems[ 0 ] = x; // initialize sentinel // Percolate up int hole = size( ); for( ; lessThan( theItems[ hole / 2 ], x ); hole /= 2 ) theItems[ hole ] = theItems[ hole / 2 ]; theItems[ hole ] = x; } template void priority_queue::pop( ) { if( empty( ) ) throw UnderflowException( "Cannot pop an empty priority queue" ); int hole = 1; int child; Object tmp = theItems.back( ); theItems.pop_back( ); int theSize = size( ); for( ; hole * 2 <= theSize; hole = child ) { child = hole * 2; if( child != theSize && lessThan( theItems[ child ], theItems[ child + 1 ] ) ) child++; if( lessThan( tmp, theItems[ child ] ) ) theItems[ hole ] = theItems[ child ]; else break; } if( !empty( ) ) theItems[ hole ] = tmp; } #include "EndConv.h" #endif