Question: c++ help #ifndef BINARY_HEAP_H #define BINARY_HEAP_H #include #include #include using namespace std; // BinaryHeap class // // CONSTRUCTION: with an optional capacity (that defaults to
c++ help
#ifndef BINARY_HEAP_H #define BINARY_HEAP_H #include#include #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 // C findMin( ) --> Return smallest item // bool isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items template class BinaryHeap { public: BinaryHeap( int capacity = 100 ) : array( capacity + 1 ), currentSize{ 0 } { } bool isEmpty( ) const { return currentSize == 0; } /** * Find the smallest item in the priority queue. * Return the smallest item */ const C & findMin( ) const { assert(!isEmpty()); return array[ 1 ]; } /** * Insert item x, allowing duplicates. */ void insert( const C & x ) { if( currentSize == array.size( ) - 1 ) array.resize( array.size( ) * 2 ); // Percolate up int hole = ++currentSize; C copy = x; array[ 0 ] = copy; for( ; x 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; C tmp = array[ hole ]; for( ; hole * 2 here is a implmenation of binary heap but its to find min not max maybe just manipulate min? I am lost on the manipulation please help. thank you.
5. (20 m arks) Max heap implementation. A max heap is a data structure that supports at least three basic operations deleteMax and insert in O(logN), and findMax (returns the maximum element) in O(1). The structure is identical to a binary heap, but the heap order property is that for any node, X, the element stored at X is larger than or equal to the elements stored in its two children. a. Please implement MaxHeap class template in MaxHeap.h. b. Please write an application program a4q5.cpp that contains main) function. The main () function, 1). creates a max heap with MaxHeapmaxheap, 2). prompt user to enter a sequence of int values, and call insert member function to insert these values in maxheap one by one, 3). repeatedly print the maximal element by calling findMax function and remove the maximum by calling deleteMax until maxheap is empty
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
