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 #include

using namespace std;

template class Less { public: bool operator()(const KeyType &a, const KeyType &b) const { return a

template > 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 #include #include

using namespace std;

#include "Heap.cpp" #include "config.h"

//-------------------------------------------------------------------- // Prototypes

void printHelp();

//-------------------------------------------------------------------- // // Declaration for the heap data item class //

template 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 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, int, Greater > testHeap(8); // Test heap TestDataItem testDataItem; // Heap data item int inputPty; // User input priority char cmd; // Input command

printHelp();

do { testHeap.showStructure(); // Output heap

cout > cmd; cmd = toupper( cmd ); // Upcase input if ( cmd == '+' ) cin >> inputPty;

switch ( cmd ) { case 'H' : printHelp(); break;

case '+' : // insert testDataItem.setPriority(inputPty); cout

case '-' : // remove testDataItem = testHeap.remove(); cout

case 'C' : // clear cout

case 'E' : // isEmpty if ( testHeap.isEmpty() ) cout

case 'F' : // isFull if ( testHeap.isFull() ) cout

#if LAB11_TEST1 case 'W' : // Programming Exercise 3 cout

case 'Q' : // Quit test program break;

default : // Invalid command cout

return 0; }

//--------------------------------------------------------------------

void printHelp() { cout

cout

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