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

C Program with android, Hello, I would like to know if you can help in C pr...

Hello, I would like to know if you can help in C programs that work on android.

Distinguish between a class and an object, Problem: (a) Distinguish bet...

Problem: (a) Distinguish between a class and an object. (b) Define instantiation. (c) What is the importance of the "this" variable in java. (d) What is encapsulation?

Jewel polishing, Byteland county is very famous for luminous jewels. Lumino...

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

Write a program to implement operator functions, Implementing Operator Func...

Implementing Operator Functions The general format of the Operator function is: return_type operator op ( argument list );   Where op is the symbol for the operator be

Write a program to calculate the average of ten numbers, Write a program to...

Write a program to calculate the average of ten numbers       #include stdio.h     /* Only this header is needed since only IO are used */     void main()     {          char

Wap to print series from 1 to 10 & find its square and cube, # include stdi...

# include stdio.h> # include conio.h> # include math.h>   void main () { int a=1,sqr=0,cube=0; clrscr (); while (a { sqr=pow(a,2); cube=pow(a,3);

Program''s, why is programming is needed now-a-days.what is the benefit of ...

why is programming is needed now-a-days.what is the benefit of colleges to apply heavy loads on students head.

Explain the shift operators, The Shift Operators There are 2 shift oper...

The Shift Operators There are 2 shift operators : left shift ( >). These are binary operators. The format is                 operand >> number or operand   The first

Logic, to calculate the amount to be paid by a customer buying yummy cupcak...

to calculate the amount to be paid by a customer buying yummy cupcakes for his birth day party

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