#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
// boolisEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Throws UnderflowException as warranted
templatetypename Comparable>
classBinaryHeap
{
public:
explicitBinaryHeap( int capacity = 100 )
: array( capacity + 1 ), currentSize{ 0 }
{
}
explicitBinaryHeap( const vector<Comparable> & items )
: array(items.size( ) + 10 ), currentSize{ items.size( ) }
{
for(inti = 0; iitems.size( ); ++i )
array[i + 1 ] = items[ i ];
buildHeap( );
}
boolisEmpty( ) const
{ returncurrentSize == 0; }
/**
* Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
const Comparable & findMin( ) const
{
if(isEmpty( ) )
throwUnderflowException{ };
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;
Comparable copy = x;
array[ 0 ] = std::move( copy );
for( ; x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( array[ 0 ] );
}
/**
* Insert item x, allowing duplicates.
*/
void insert( 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 ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( x );
}
/**
* Remove the minimum item.
* Throws UnderflowException if empty.
*/
voiddeleteMin( )
{
if(isEmpty( ) )
throwUnderflowException{ };
array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}
/**
* Remove the minimum item and place it in minItem.
* Throws Underflow if empty.
*/
voiddeleteMin( Comparable & minItem )
{
if(isEmpty( ) )
throwUnderflowException{ };
minItem = std::move( array[ 1 ] );
array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}
voidmakeEmpty( )
{ 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.
*/
voidbuildHeap( )
{
for(inti = currentSize / 2; i > 0; --i )
percolateDown(i );
}
/**
* Internal method to percolate down in the heap.
* hole is the index at which the percolate begins.
*/
voidpercolateDown( int hole )
{
int child;
Comparable tmp = std::move( 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 ] = std::move( array[ child ] );
else
break;
}
array[ hole ] = std::move( tmp );
}
};
#endif