Write valid C++ code to modify the class BinaryHeap listed below to support the
ID: 3819750 • Letter: W
Question
Write valid C++ code to modify the class BinaryHeap listed below to support the following operations:
(a) decreaseKey(p, d) - Lowers the value of the item at position p by a positive amount d.
(b) increaseKey(p, d) - Increases the value of the item at position p by a positive amount d.
(c) remove(p) - Removes the node at position p.
Also write code to test your routines above. Thank you!
----------------------------------------------------------------------------------------------------------
#ifndef BINARY_HEAP_H
#define BINARY_HEAP_H
#include "dsexceptions.h"
#include
using namespace std;
// 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( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Throws UnderflowException as warranted
template
class BinaryHeap
{
public:
explicit BinaryHeap( int capacity = 100 )
: array( capacity + 1 ), currentSize{ 0 }
{
}
explicit BinaryHeap( const vector & items )
: array( items.size( ) + 10 ), currentSize{ items.size( ) }
{
for( int i = 0; i < items.size( ); ++i )
array[ i + 1 ] = items[ i ];
buildHeap( );
}
bool isEmpty( ) const
{ return currentSize == 0; }
/**
* Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
const Comparable & findMin( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
return array[ 1 ];
}
/**
* Insert item x, allowing duplicates.
*/
void insert( const Comparable & x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );
// Percolate up
int hole = ++currentSize;
Comparable copy = x;
array[ 0 ] = std::move( copy );
for( ; x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( array[ 0 ] );
}
/**
* Insert item x, allowing duplicates.
*/
void insert( Comparable && x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );
// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( x );
}
/**
* Remove the minimum item.
* Throws UnderflowException if empty.
*/
void deleteMin( )
{
if( isEmpty( ) )
throw UnderflowException{ };
array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}
/**
* Remove the minimum item and place it in minItem.
* Throws Underflow if empty.
*/
void deleteMin( Comparable & minItem )
{
if( isEmpty( ) )
throw UnderflowException{ };
minItem = std::move( array[ 1 ] );
array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}
void makeEmpty( )
{ currentSize = 0; }
private:
int currentSize; // Number of elements in heap
vector array; // The heap array
/**
* Establish heap order property from an arbitrary
* arrangement of items. Runs in linear time.
*/
void buildHeap( )
{
for( int i = currentSize / 2; i > 0; --i )
percolateDown( i );
}
/**
* Internal method to percolate down in the heap.
* hole is the index at which the percolate begins.
*/
void percolateDown( int hole )
{
int child;
Comparable tmp = std::move( array[ hole ] );
for( ; hole * 2 <= currentSize; hole = child )
{
child = hole * 2;
if( child != currentSize && array[ child + 1 ] < array[ child ] )
++child;
if( array[ child ] < tmp )
array[ hole ] = std::move( array[ child ] );
else
break;
}
array[ hole ] = std::move( tmp );
}
};
#endif
Explanation / Answer
#ifndef BINARY_HEAP_H
#define BINARY_HEAP_H
#include "dsexceptions.h"
#include
using namespace std;
// 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( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Throws UnderflowException as warranted
template
class BinaryHeap
{
public:
explicit BinaryHeap( int capacity = 100 )
: array( capacity + 1 ), currentSize{ 0 }
{
}
explicit BinaryHeap( const vector & items )
: array( items.size( ) + 10 ), currentSize{ items.size( ) }
{
for( int i = 0; i < items.size( ); ++i )
array[ i + 1 ] = items[ i ];
buildHeap( );
}
bool isEmpty( ) const
{ return currentSize == 0; }
/**
* Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
const Comparable & findMin( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
return array[ 1 ];
}
/**
* Insert item x, allowing duplicates.
*/
void insert( const Comparable & x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );
// Percolate up
int hole = ++currentSize;
Comparable copy = x;
array[ 0 ] = std::move( copy );
for( ; x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( array[ 0 ] );
}
/**
* Insert item x, allowing duplicates.
*/
void insert( Comparable && x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );
// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( x );
}
/**
* Remove the minimum item.
* Throws UnderflowException if empty.
*/
void deleteMin( )
{
if( isEmpty( ) )
throw UnderflowException{ };
array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}
/**
* Remove the minimum item and place it in minItem.
* Throws Underflow if empty.
*/
void deleteMin( Comparable & minItem )
{
if( isEmpty( ) )
throw UnderflowException{ };
minItem = std::move( array[ 1 ] );
array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}
void makeEmpty( )
{ currentSize = 0; }
private:
int currentSize; // Number of elements in heap
vector array; // The heap array
/**
* Establish heap order property from an arbitrary
* arrangement of items. Runs in linear time.
*/
void buildHeap( )
{
for( int i = currentSize / 2; i > 0; --i )
percolateDown( i );
}
/**
* Internal method to percolate down in the heap.
* hole is the index at which the percolate begins.
*/
void percolateDown( int hole )
{
int child;
Comparable tmp = std::move( array[ hole ] );
for( ; hole * 2 <= currentSize; hole = child )
{
child = hole * 2;
if( child != currentSize && array[ child + 1 ] < array[ child ] )
++child;
if( array[ child ] < tmp )
array[ hole ] = std::move( array[ child ] );
else
break;
}
array[ hole ] = std::move( tmp );
}
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.