Implement binary heap in c++?, C/C++ Programming

Assignment Help:

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;

}

 


Related Discussions:- Implement binary heap in c++?

Data structure, how to convert a general tree into binary tree with example...

how to convert a general tree into binary tree with example

Explain member functions of a class, Member Functions of a Class A memb...

Member Functions of a Class A member function of the class is similar as an ordinary function. Its declaration in a class template must explain its return value as well as the

Calculate the average assignment grade, 1. The main program must be in a fi...

1. The main program must be in a file called A4.cpp 2. The data must be read in from a data file.  The user must enter the filename.  A sample data file will be provided on Mood

Optimize and profile a c++ library for speed, Optimize and Profile a C++ li...

Optimize and Profile a C++ library for speed Project Description:  Optimize and Profile an existing C++ library for speed. This library uses OpenMP and OpenCV and C++ stan

C program for exchange first & last character, Normal 0 false ...

Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

Pointer declaration for member function, P o i n t e r d...

P o i n t e r d e c l a r a t i o n f o r me m b e r f un c t i o n : M e t h o d 1 : W h e n C l a ss i s n o t

Araay, create two array names and grade .in first array you have to store t...

create two array names and grade .in first array you have to store thease 10 names 1.a,2.3.r,4.s,5.l,6.k,7.n,8.b,9.z,10.d you have to enter grades for thease students.te program mu

Declaring Integer variables with an example, How do you declare an integer ...

How do you declare an integer variable? Explain with an example.

Algorithm , write an algorithm to swap values without using third variable

write an algorithm to swap values without using third variable

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd