Implement the BinaryHeap ADT in a file BinaryHeap.cpp #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 // void deleteMin( ) --> Remove smallest item // void deleteMin(minItem)--> Remove smallest item and store the minimum in minItem // 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 = CAP ) : items( capacity ), 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 items[ 1 ]; } /** * Insert item x, allowing duplicates. */ void insert( const C & x ) { if( currentSize == items.size( ) - 1 ) items.resize( items.size( ) * 2 ); // Percolate up int hole = ++currentSize; C copy = x; items[ 0 ] = copy; for( ; x < items[ hole / 2 ]; hole /= 2 ) items[ hole ] = items[ hole / 2 ]; items[ hole ] = items[ 0 ]; } /** * Remove the minimum item. */ void deleteMin() { assert(!isEmpty()); items[1] = items[currentSize]; currentSize = currentSize - 1; percolateDown(1); } /** * Remove the minimum item and place it in minItem. */ void deleteMin(C& minItem) { assert(!isEmpty()); minItem = items[1]; items[1] = items[currentSize]; currentSize = currentSize - 1; percolateDown(1); } void makeEmpty() { currentSize = 0; } static const int CAP = 100; private: int currentSize; // Number of elements in heap vector items; // 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 = items[ hole ]; for( ; hole * 2 <= currentSize; hole = child ) { child = hole * 2; if( child != currentSize && items[ child + 1 ] < items[ child ] ) ++child; if( items[ child ] < tmp ) items[ hole ] = items[ child ]; else break; } items[ hole ] = tmp;
Implement the BinaryHeap ADT in a file BinaryHeap.cpp
#ifndef BINARY_HEAP_H
#define BINARY_HEAP_H
#include <assert.h>
#include <
#include <iostream>
using namespace std;
// BinaryHeap class
//
// CONSTRUCTION: with an optional capacity (that defaults to 100)
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void deleteMin( ) --> Remove smallest item
// void deleteMin(minItem)--> Remove smallest item and store the minimum in minItem
// C findMin( ) --> Return smallest item
// bool isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
template <typename C>
class BinaryHeap
{ public:
BinaryHeap( int capacity = CAP ) : items( capacity ), 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 items[ 1 ];
}
/**
* Insert item x, allowing duplicates.
*/
void insert( const C & x )
{
if( currentSize == items.size( ) - 1 )
items.resize( items.size( ) * 2 );
// Percolate up
int hole = ++currentSize;
C copy = x;
items[ 0 ] = copy;
for( ; x < items[ hole / 2 ]; hole /= 2 )
items[ hole ] = items[ hole / 2 ];
items[ hole ] = items[ 0 ];
}
/**
* Remove the minimum item.
*/
void deleteMin()
{
assert(!isEmpty());
items[1] = items[currentSize];
currentSize = currentSize - 1;
percolateDown(1);
}
/**
* Remove the minimum item and place it in minItem.
*/
void deleteMin(C& minItem)
{
assert(!isEmpty());
minItem = items[1];
items[1] = items[currentSize];
currentSize = currentSize - 1;
percolateDown(1);
}
void makeEmpty()
{
currentSize = 0;
}
static const int CAP = 100;
private:
int currentSize; // Number of elements in heap
vector<C> items; // 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 = items[ hole ];
for( ; hole * 2 <= currentSize; hole = child )
{
child = hole * 2;
if( child != currentSize && items[ child + 1 ] < items[ child ] )
++child;
if( items[ child ] < tmp )
items[ hole ] = items[ child ];
else
break;
}
items[ hole ] = tmp;
}
};
#endif
![Defines a public member function printJobs () in Binaryäeap.cpp which prints out the print jobs in
printQueue.
• Calls the printJobs () member function in main () to print out the print jobs.
• Prompts user to enter n - the number of jobs that the printer will run.
• Calls deleteMin () member function n times.
• Calls 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](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F7faf7689-a333-4c1a-bc57-3ca739f95b44%2F7834a18c-3b88-4905-8af5-a3ccce5fe926%2Fmd5w8sk_processed.jpeg&w=3840&q=75)
![](/static/compass_v2/shared-icons/check-mark.png)
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 5 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Computer Networking: A Top-Down Approach (7th Edi…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
![Computer Organization and Design MIPS Edition, Fi…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
![Network+ Guide to Networks (MindTap Course List)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
![Computer Networking: A Top-Down Approach (7th Edi…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
![Computer Organization and Design MIPS Edition, Fi…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
![Network+ Guide to Networks (MindTap Course List)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
![Concepts of Database Management](https://www.bartleby.com/isbn_cover_images/9781337093422/9781337093422_smallCoverImage.gif)
![Prelude to Programming](https://www.bartleby.com/isbn_cover_images/9780133750423/9780133750423_smallCoverImage.jpg)
![Sc Business Data Communications and Networking, T…](https://www.bartleby.com/isbn_cover_images/9781119368830/9781119368830_smallCoverImage.gif)