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

How can define an array, Q: How can Define an Array? An Array is define...

Q: How can Define an Array? An Array is defined in much the alike manner as ordinary variables except that every array name must be accompanied by a size specification (that is

External iterator and an internal iterator, What is the difference between ...

What is the difference between an external iterator and an internal iterator? Ans) An internal iterator is executed with member functions of the class that has items to step th

Explain public derivation, Public derivation Public derivations are muc...

Public derivation Public derivations are much more common than private derivations. In this situation: The private members inherited from the base class are inaccessible

C prg, main() { int a[5]={1,3,6,7,0}; int *b; b=&a[2]; } The value of b[-1]...

main() { int a[5]={1,3,6,7,0}; int *b; b=&a[2]; } The value of b[-1] is

Quick sort , Hi, I need quick sort program without using recursion

Hi, I need quick sort program without using recursion

Star, Write a program that finds the minimum total number of shelves, inclu...

Write a program that finds the minimum total number of shelves, including the initial one required for this loading process.

Write a program to test the class, Problem Implement a class called emp...

Problem Implement a class called employee that contains name, employee number and department code. Include a member function getdata() to get data from user and store it in the

Explain the loop statements in computer programming, Explain the Loop State...

Explain the Loop Statements in Computer Programming? 1. C gives you a choice of three kinds of loop, while, do while and for. 2. The while loop remain repeating an action until

Output, i need my home work

i need my home work

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