Heap code in C++
template <class eType>
void Heap<eType>::deleteMin( eType & minItem )
{
if( isEmpty( ) ) {
cout << "heap is empty.“ << endl;
return;
}
minItem = array[ 1 ];
array[ 1 ] = array[ currentSize-- ];
percolateDown( 1 );
}
Lecture No.32
Data Structure
Dr. Sohail Aslam
Heap code in C++
// hole is the index at which the percolate begins.
template <class eType>
void Heap<eType>::percolateDown( int hole )
{
int child;
eType tmp = array[ hole ];
for( ; hole * 2 <= currentSize; hole = child )
{
child = hole * 2;
if( child != currentSize &&
array[child+1] < array[ child ] )
child++; // right child is smaller
if( array[ child ] < tmp )
array[ hole ] = array[ child ];
else break;
}
array[ hole ] = tmp;
}
Heap code in C++
template <class eType>
const eType& Heap<eType>::getMin( )
{
if( !isEmpty( ) )
return array[ 1 ];
}
template <class eType>
void Heap<eType>::buildHeap(eType* anArray, int n )
{
for(int i = 1; i <= n; i++)
array[i] = anArray[i-1];
currentSize = n;
for( int i = currentSize / 2; i > 0; i-- )
percolateDown( i );
}
Heap code in C++
template <class eType>
bool Heap<eType>::isEmpty( )
{
return currentSize == 0;
}
template <class eType>
bool Heap<eType>::isFull( )
{
return currentSize == capacity;
}
template <class eType>
int Heap<eType>::getSize( )
{
return currentSize;
}