A:BinaryHeap.h
------------
#ifndef BINARY_HEAP_H_
#define BINARY_HEAP_H_
#include "dsexceptions.h"
#include "vector.h"
// 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( ) --> if empty, Return true; else false
// bool isFull( ) --> if full , Return true; else false
// void makeEmpty( ) --> Eliminate all items
// ***********ERRORS*************
// Throws Underflow & Overflow as necessary
template
class BinaryHeap
{
public:
explicit BinaryHeap( int capacity = 100 );
bool isEmpty( ) const;
bool isFull( ) const;
const Comparable & findMin( ) const;
void insert( const Comparable & x );
void deleteMin( );
void deleteMin( Comparable & minItem );
void makeEmpty( );
private:
int currentSize; // Number of elements in heap vector array; // The heap array
void buildHeap( );
void percolateDown( int hole );
};
#endif
BinaryHeap.cpp
--------------
#include "BinaryHeap.h"
/**
* Construct the binary heap.
* Capacity means capacity of binary heap.
*/
template
BinaryHeap::BinaryHeap( int capacity )
: array( capacity + 1 ), currentSize( 0 )
{
}
/**
* Insert item x in the priority queue, maintaining heap order.
* Duplicates are allowed.
* Throw Overflow if container is full.
*/
template
void BinaryHeap::insert( const Comparable & x )
{
if( isFull( ) )
throw Overflow( );
// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[ hole ] = x;
}
/**
* Determine the smallest item in the priority queue.
* Return the smallest item, or if empty , throw Underflow.
*/
template
const Comparable & BinaryHeap::findMin( ) const
{
if( isEmpty( ) ) throw Underflow( ); return array[ 1 ];
}
/**
* From priority queue remove smallest item.
* Throw Underflow if empty.
*/
template
void BinaryHeap::deleteMin( )
{
if( isEmpty( ) )
throw Underflow( );
array[ 1 ] = array[ currentSize-- ];
percolateDown( 1 );
}
/**
* From the priority queue eliminate the smallest item
* and place it in minItem. Throw Underflow if empty.
*/
template
void BinaryHeap::deleteMin( Comparable & minItem )
{
if( isEmpty( ) )
throw Underflow( );
minItem = array[ 1 ];
array[ 1 ] = array[ currentSize-- ];
percolateDown( 1 );
}
/**
* From arbitrary establish heap order property
* Arrangement of items. Runs in linear time.
*/
template
void BinaryHeap::buildHeap( )
{
for( int i = currentSize / 2; i > 0; i-- )
percolateDown( i );
}
/**
* Test if the priority queue is empty logically.
* Return true if empty, or else false.
*/
template
bool BinaryHeap::isEmpty( ) const
{
return currentSize == 0;
}
/**
* Test if priority queue is logically full.
* Return true if full, false otherwise.
*/
template
bool BinaryHeap::isFull( ) const
{
return currentSize == array.size( ) - 1;
}
/**
* Logically make priority queue empty.
*/
template
void BinaryHeap::makeEmpty( )
{
currentSize = 0;
}
/**
* To percolate down, internal technique in the heap.
* hole is the index whereupon the percolate begins.
*/
template
void BinaryHeap::percolateDown( int hole )
{
/* 1*/ int child;
/* 2*/ Comparable tmp = array[ hole ];
/* 3*/ for( ; hole * 2 <= currentSize; hole = child )
{
/* 4*/ child = hole * 2;
/* 5*/ if( child != currentSize && array[ child + 1 ] < array[ child ] )
/* 6*/ child++;
/* 7*/ if( array[ child ] < tmp )
/* 8*/ array[ hole ] = array[ child ];
else
/* 9*/ break;
}
/*10*/ array[ hole ] = tmp;
}
TestBinaryHeap.cpp
------------------
#include
#include "BinaryHeap.h"
#include "dsexceptions.h"
// Test program int main( )
{
int numItems = 10000; BinaryHeap h( numItems ); int i = 37;
int x;
try
{
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 );
h.insert( i = 999999 ); // Should overflow
}
catch( Overflow )
{ cout << "Overflow (expected)! " << i << endl; }
return 0;
}