please use microsoft visual studio. please include screenshots of compiled code.

Implement the Heap ADT (100 points) [the declaration is given in Heap.h]. Implement the following operations:

constructor, copy constructor, assignment operator, destructor; (40 pts)

insert, remove; (40 pts)

clear, isEmpty. (20 pts)

Config.h

/**

* Heap class configuration file.

* Activate test #N by defining the corresponding LAB11_TESTN to have the value 1.

*/

#define LAB11_TEST1 0 // Programming Exercise 3: writeLevels

Heap.h

#ifndef HEAP_H

#define HEAP_H

#pragma warning( disable : 4290 )

#include

#include

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 >

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

Heap.cpp

#include "Heap.h"

template < typename DataType, typename KeyType, typename Comparator >

Heap::Heap ( int maxNumber = DEFAULT_MAX_HEAP_SIZE )

{

}

template < typename DataType, typename KeyType, typename Comparator >

Heap::Heap ( const Heap& other )

{

}

template < typename DataType, typename KeyType, typename Comparator >

Heap& Heap::operator= ( const Heap& other )

{

}

template < typename DataType, typename KeyType, typename Comparator >

Heap::~Heap ()

{

}

template < typename DataType, typename KeyType, typename Comparator >

void Heap::insert ( const DataType &newDataItem )

throw ( logic_error )

{

}

template < typename DataType, typename KeyType, typename Comparator >

DataType Heap::remove () throw ( logic_error )

{

DataType temp;

return temp;

}

template < typename DataType, typename KeyType, typename Comparator >

void Heap::clear ()

{

}

template < typename DataType, typename KeyType, typename Comparator >

bool Heap::isEmpty () const

{

return false;

}

template < typename DataType, typename KeyType, typename Comparator >

bool Heap::isFull () const

{

return false;

}

#include "show11.cpp"

show11.cpp

#include "heap.h"

//-------------------------------------------------------------------- // // Laboratory 11 show11.cpp // // Array implementation of the showStructure operation for the // Heap ADT // //--------------------------------------------------------------------

template < typename DataType, typename KeyType, typename Comparator > void Heap:: showStructure () const

// Outputs the priorities of the data items in a heap in both array // and tree form. If the heap is empty, outputs "Empty heap". This // operation is intended for testing/debugging purposes only.

{ int j; // Loop counter

cout << endl; if ( size == 0 ) cout << "Empty heap" << endl; else { cout << "size = " << size << endl; // Output array form for ( j = 0 ; j < maxSize ; j++ ) cout << j << "\t"; cout << endl; for ( j = 0 ; j < size ; j++ ) cout << dataItems[j].getPriority() << "\t"; cout << endl << endl; showSubtree(0,0); // Output tree form } }

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

template < typename DataType, typename KeyType, typename Comparator > void Heap:: showSubtree ( int index, int level ) const

// Helper function for the showStructure() function. Outputs the // subtree (subheap) whose root is stored in dataItems[index]. Argument // level is the level of this dataItems within the tree.

{ int j; // Loop counter

if ( index < size ) { showSubtree(2*index+2,level+1); // Output right subtree for ( j = 0 ; j < level ; j++ ) // Tab over to level cout << "\t"; cout << " " << dataItems[index].getPriority(); // Output dataItems's priority if ( 2*index+2 < size ) // Output "connector" cout << "<"; else if ( 2*index+1 < size ) cout << "\\"; cout << endl; showSubtree(2*index+1,level+1); // Output left subtree } }

test11.cpp

#include

#include

#include

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, 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 << 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;

}