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++?

Contacts manager data and image facebook sync, Project Description: coll...

Project Description: collect / modify person records / photo images/ lookup / facebook iphone and ipad App basic function : 1 user will configure facebook connection

Playback pattern sequences, This task involves creating a new class(es) tha...

This task involves creating a new class(es) that will allow the system to playback pattern sequences using the Neo  Freerunner  hardware. The first thing to note is that the vibrat

Decode the code, c++ coding decode the letters from numbers

c++ coding decode the letters from numbers

Luminous jewel polishing neckiace, Byteland county is very famous for lumin...

Byteland county is very famous for luminous jewels. Luminous jewels are used in making beautiful necklaces. A necklace consists of various luminous jewels of particular colour. Nec

Padovan string, padovan string for n natural numbers p(n)=1,p(n)=2,p(n)=3 a...

padovan string for n natural numbers p(n)=1,p(n)=2,p(n)=3 and use padovan formul to get output 1

Define an asset base class, a) Define an Asset base class that provides the...

a) Define an Asset base class that provides the following method: class Asset { public:      virtual double getValue()=0; };   This will be the base class for both stock an

Word counting, Task Your task is to write a program, words, that reports i...

Task Your task is to write a program, words, that reports information about the number of words read from its standard input. For example, if the file qbf.txtcontains the text th

Working a homework programming assignment in C++, I am working on a program...

I am working on a program that allows a player to play a game against the computer. In this game the player can only chose to draw 1, 2, or 3 toothpicks. How do I make restrictions

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