In C++

Implement the BinaryHeap ADT in a file BinaryHeap.h as shown below.

// BinaryHeap.h #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[ hole / 2 ]; hole /= 2 ) array[ hole ] = array[ hole / 2 ]; array[ hole ] = array[ 0 ]; } /** * Remove the minimum item. */ void deleteMin( ) { assert(!isEmpty()); array[ 1 ] = array[ currentSize ]; currentSize = currentSize - 1; percolateDown( 1 ); } /** * Remove the minimum item and place it in minItem. */ void deleteMin( C & minItem ) { assert(!isEmpty()); minItem = array[ 1 ]; array[ 1 ] = array[ currentSize ]; currentSize = currentSize - 1; 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; C tmp = 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 ] = array[ child ]; else break; } array[ hole ] = tmp; } }; #endif 

Program your own file lab10.cpp in which your main() function will test the new data structure. The main() function,

• Declare an instance of BinaryHeap BinaryHeap printQueue; suitable to hold a queue of print jobs.
• Prompt user to enter a sequence of priority values of print jobs, insert these print jobs into the printQueue.
• Define a public member function printJobs() in BinaryHeap.h which prints out the print jobs in printQueue.
• Call the printJobs() member function in main()to print out the print jobs.
• Prompt user to enter n - the number of jobs that the print will run.
• Call deleteMin() member function n times.
• Call the printJobs() member function in main()to print out the remaining print jobs.

The expected result:

The priority of print job? 6 The priority of print job? 20 The priority of print job? 5 The priority of print job? 3 The priority of print job? 1 The priority of print job? 36 The priority of print job? 8 The priority of print job? 12 The priority of print job? 6 The print jobs: 1 3 6 6 5 36 8 20 12 The number of jobs the printer will run? 3 The print jobs: 6 8 6 20 12 36