Write in C++ only Header file Heap.h //-----------------------------------------
ID: 3848826 • Letter: W
Question
Write in C++ only
Header file Heap.h
//--------------------------------------------------------------------
//
// Laboratory 12 Heap.h
//
// Class declaration for the array implementation of the Heap ADataType
//
//--------------------------------------------------------------------
#ifndef HEAP_H
#define HEAP_H
#include <stdexcept>
#include <iostream>
using namespace std;
template < typename KeyType=int >
class Less {
public:
bool operator()(const KeyType &a, const KeyType &b) const { return a < b; }
};
template < typename DataType, typename KeyType=int, typename Comparator=Less<KeyType> >
class Heap
{
public:
static const int DEFAULT_MAX_HEAP_SIZE = 10; // Default maximum heap size
// Constructor
Heap ( int maxNumber = DEFAULT_MAX_HEAP_SIZE ); // Default constructor + basic constr
Heap ( const Heap& other ); // Copy constructor
Heap& operator= ( const Heap& other ); // Overloaded assignment operator
// Destructor
~Heap ();
// Heap manipulation operations
void insert ( const DataType &newDataItem ) // Insert a data item
throw ( logic_error );
DataType remove () throw ( logic_error ); // Remove max priority element
void clear (); // Clear heap
// Heap status operations
bool isEmpty () const; // Heap is empty
bool isFull () const; // Heap is full
// Output the heap structure -- used in testing/debugging
void showStructure () const;
// Programming exercise #3 operation
void writeLevels () const; // Output in level order
private:
// Recursive helper of the showStructure() function
void showSubtree ( int index, int level ) const;
// Data members
int maxSize, // Maximum number of elements in the heap
size; // Actual number of elements in the heap
DataType *dataItems; // Array containing the heap elements
Comparator comparator;
};
#endif //#ifndef HEAP_H
Test11.cpp code
//--------------------------------------------------------------------
//
// Laboratory 11 test11.cpp
//
// Test program for the operations in the Heap ADT
//
//--------------------------------------------------------------------
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
#include "Heap.cpp"
#include "config.h"
//--------------------------------------------------------------------
// Prototypes
void printHelp();
//--------------------------------------------------------------------
//
// Declaration for the heap data item class
//
template < typename KeyType >
class TestDataItem
{
public:
TestDataItem ()
{ priority = -1; }
void setPriority ( KeyType newPty )
{ priority = newPty; } // Set the priority
KeyType getPriority () const
{ return priority; } // Returns the priority
private:
KeyType priority; // Priority for the data item
};
template < typename KeyType=int >
class Greater {
public:
bool operator()( const KeyType &a, const KeyType &b) const { return a > b; }
};
int main()
{
// Greater<> uses the default int type for its KeyType
Heap<TestDataItem<int>, int, Greater<> > testHeap(8); // Test heap
TestDataItem<int> testDataItem; // Heap data item
int inputPty; // User input priority
char cmd; // Input command
printHelp();
do
{
testHeap.showStructure(); // Output heap
cout << endl << "Command: "; // Read command
cin >> cmd;
cmd = toupper( cmd ); // Upcase input
if ( cmd == '+' )
cin >> inputPty;
switch ( cmd )
{
case 'H' :
printHelp();
break;
case '+' : // insert
testDataItem.setPriority(inputPty);
cout << "Insert : priority = " << testDataItem.getPriority()
<< endl;
testHeap.insert(testDataItem);
break;
case '-' : // remove
testDataItem = testHeap.remove();
cout << "Removed data item : "
<< " priority = " << testDataItem.getPriority() << endl;
break;
case 'C' : // clear
cout << "Clear the heap" << endl;
testHeap.clear();
break;
case 'E' : // isEmpty
if ( testHeap.isEmpty() )
cout << "Heap is empty" << endl;
else
cout << "Heap is NOT empty" << endl;
break;
case 'F' : // isFull
if ( testHeap.isFull() )
cout << "Heap is full" << endl;
else
cout << "Heap is NOT full" << endl;
break;
#if LAB11_TEST1
case 'W' : // Programming Exercise 3
cout << "Levels :" << endl;
testHeap.writeLevels();
break;
#endif // LAB11_TEST1
case 'Q' : // Quit test program
break;
default : // Invalid command
cout << "Inactive or invalid command" << endl;
}
}
while ( cmd != 'Q' );
return 0;
}
//--------------------------------------------------------------------
void printHelp()
{
cout << endl << "Commands:" << endl;
cout << " H : Help (displays this message)" << endl;
cout << " +pty : Insert data item with priority pty" << endl;
cout << " - : Remove highest priority data item" << endl;
cout << " C : Clear the heap" << endl;
cout << " E : Empty heap?" << endl;
cout << " F : Full heap?" << endl;
cout << " W : Write levels ("
#if LAB11_TEST1
"Active "
#else
"Inactive "
#endif //LAB11_TEST1
<< ": Programming Exercise 3)" << endl;
cout << " Q : Quit the test program" << endl;
cout << endl;
}
Thank You
Heap ADT Type. Each data item has heap Data items seneric e rahe within the to in a heap are relative that priorities are "or obiects Note priority, The is to additional operators, as imetion etyve it quite that basic relational usually likely six item's Type must the data Data returns a ity that eatra For each data item E in the tre an of Structure complete or equ to Es priority The data items form a are less than have Operations HEAP. 12E) Reap int max Number MAx Requirements None memory for a heap Constructor, creates an empty heap. A enough Number data items, containi Heap const He other Requirements Results: the object to be an equivalent copy of other. copy constructor. Initializes Heap& operator const Heap other Requirements None Results heap to be equivalent to the other Heap and overloaded assignment operator. Sets the returns a reference to this object. -Heap Requirements: None Results: Destructor. Deallocates (frees the memory used to store the heap.Explanation / Answer
void printHelp()
{
cout << endl << "Commands:" << endl;
cout << " H : Help (displays this message)" << endl;
cout << " +pty : Insert data item with priority pty" << endl;
cout << " - : Remove highest priority data item" << endl;
cout << " C : Clear the heap" << endl;
cout << " E : Empty heap?" << endl;
cout << " F : Full heap?" << endl;
cout << " W : Write levels ("
#if LAB11_TEST1
"Active "
#else
"Inactive "
#endif //LAB11_TEST1
<< ": Programming Exercise 3)" << endl;
cout << " Q : Quit the test program" << endl;
cout << endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.