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

Define generic bitwise operations, Define Generic Bitwise Operations? ...

Define Generic Bitwise Operations? Bitwise operators only work on an incomplete number of types int and char. It turns out there's above one kind of int. In particular there's

Time table, programme for time table in c++

programme for time table in c++

Explain bit-wise operators, Bit-wise Operators Some applications requir...

Bit-wise Operators Some applications require operations to be done on dissimilar bits of a byte separately. Bit-wise operators offer a facility to do just that. There are vario

Algorithem, algorithem of compound interest

algorithem of compound interest

Described smart pointer?, A: A smart pointer is a C++ class which mimics a ...

A: A smart pointer is a C++ class which mimics a regular pointer in syntax and some semantics, however it does more. Since smart pointers to distinct types of objects tend to have

C programming, Write a program that keeps record of football results. Progr...

Write a program that keeps record of football results. Program stores following information about each match: Description Type and/or size name of home team max. 25 characters name

Program to write c++ program, program to write superposition of waves using...

program to write superposition of waves using class and objects

Strings, A string S is said to be "Super ASCII", if it contains the charact...

A string S is said to be "Super ASCII", if it contains the character frequency equal to their ascii values. String will contain only lower case alphabets (''a''-''z'') and the asci

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