please use visual studio and make the program and all the function runs properly
ID: 3717763 • Letter: P
Question
please use visual studio and make the program and all the function runs properly. Need this ASAP.thank you.
----------------------------------------------------------------------------------------------------------
Implement the following two functions:
moveDown() - similar to remove() function, except that it doesn’t remove node and could work with a portion of the tree. (50 pts)
writeLevel() - output the data items in the level order. (50 pts
--------------------------------------------------------------------------------
//Heap.h
#ifndef HEAP_H
#define HEAP_H
#pragma warning( disable : 4290 )
#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
void moveDown(DataType dataItem[], int root, int size);
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<DataType, KeyType, Comparator>::Heap(int maxNumber = DEFAULT_MAX_HEAP_SIZE)
{
maxSize = maxNumber;
size = 0;
dataItems = new DataType[maxSize];
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>::Heap(const Heap& other)
{
*this = other;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>& Heap<DataType, KeyType, Comparator>::operator= (const Heap& other)
{
if (this == &other)
return *this;
if (isEmpty() == false)
clear();
size = other.size;
maxSize = other.maxSize;
for (inti = 0; i < size; i++)
dataItems[i] = other.dataItems[i];
return *this;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>::~Heap()
{
clear();
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType, KeyType, Comparator>::insert(const DataType &newDataItem)
throw (logic_error)
{
if (isFull() == false)
{
int index = size;
comparator compare;
dataItems[size] = newDataItem;
while (compare(dataItems[index].getPriority(), dataItems[(index - 1) / 2].getPriority()))
{
DataType data = dataItems[index];
dataItems[index] = dataItems[(inex - 1) / 2];
dataItems[(index - 1) / 2] = data;
index = (index - 1) / 2;
}
size++;
}
else
{
throw logic_error("Full List.")
}
}
?
template < typename DataType, typename KeyType, typename Comparator >
DataType Heap<DataType, KeyType, Comparator>::remove() throw (logic_error)
{
if (isEmpty() == true)
{
throw logic_error("Empty List");
}
size--;
DataType returnData = dataItems[0];
dataItems[0] = dataItems[size];
int index = 0;
while (index < size)
{
Comparator compare;
if ((index * 2) + 2 <= size)
{
if (compare(dataItems[index].getPriority(),dataItems[(index * 2) + 1].getPriority()) &&
compare(dataItems[index].getPriority(), dataItems[(index * 2) + 2].getPriority()))
{
return returnData;
}
else if (compare(dataItems[(index * 2) + 2].getPriority(),dataItems[(index * 2) + 1].getPriority()))
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[(index * 2) + 2];
dataItems[(index * 2) + 2] = temp;
index = (index * 2) + 2;
}
else
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[index + 1];
dataItems[(index * 2) + 1] = temp;
index = (index * 2) + 1;
}
}
else if ((index * 2) + 1 <= size)
{
if (compare(dataItems[(index * 2) + 1].getPriority(),
dataItems[index].getPriority()))
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[(index * 2) + 1];
dataItems[(index * 2) + 1] = temp;
index = (index * 2) + 1;
}
else
{
return returnData;
}
}
else
{
return returnData;
}
}
return returnData;
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType, KeyType, Comparator>::clear()
{
delete[]dataItems;
size = 0;
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType, KeyType, Comparator>::isEmpty() const
{
return (size == 0);
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType, KeyType, Comparator>::isFull() const
{
return (size == maxSize);
}
template<typename DataType, typename KeyType, typename Comparator>
void Heap<DataType, KeyType, Comparator>::writeLevels() const
{
}
template<typename DataType, typename KeyType, typename Comparator>
void Heap<DataType, KeyType, Comparator>::moveDown(DataType dataItem[], int root, int size)
{
}
#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<DataType,KeyType,Comparator>:: 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 << " ";
cout << endl;
for ( j = 0 ; j < size ; j++ )
cout << dataItems[j].getPriority() << " ";
cout << endl << endl;
showSubtree(0,0); // Output tree form
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType,KeyType,Comparator>:: 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 << " ";
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
}
}
---------------------------------------------------------------------------
//--------------------------------------------------------------------
//
// 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;
}
-----------------------------------------------------------------------------
//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 please use visual studio and make the program and all the function runs properly. Need this ASAP.
thank you.
----------------------------------------------------------------------------------------------------------
Implement the following two functions:
moveDown() - similar to remove() function, except that it doesn’t remove node and could work with a portion of the tree. (50 pts)
writeLevel() - output the data items in the level order. (50 pts
--------------------------------------------------------------------------------
//Heap.h
#ifndef HEAP_H
#define HEAP_H
#pragma warning( disable : 4290 )
#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
void moveDown(DataType dataItem[], int root, int size);
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<DataType, KeyType, Comparator>::Heap(int maxNumber = DEFAULT_MAX_HEAP_SIZE)
{
maxSize = maxNumber;
size = 0;
dataItems = new DataType[maxSize];
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>::Heap(const Heap& other)
{
*this = other;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>& Heap<DataType, KeyType, Comparator>::operator= (const Heap& other)
{
if (this == &other)
return *this;
if (isEmpty() == false)
clear();
size = other.size;
maxSize = other.maxSize;
for (inti = 0; i < size; i++)
dataItems[i] = other.dataItems[i];
return *this;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>::~Heap()
{
clear();
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType, KeyType, Comparator>::insert(const DataType &newDataItem)
throw (logic_error)
{
if (isFull() == false)
{
int index = size;
comparator compare;
dataItems[size] = newDataItem;
while (compare(dataItems[index].getPriority(), dataItems[(index - 1) / 2].getPriority()))
{
DataType data = dataItems[index];
dataItems[index] = dataItems[(inex - 1) / 2];
dataItems[(index - 1) / 2] = data;
index = (index - 1) / 2;
}
size++;
}
else
{
throw logic_error("Full List.")
}
}
?
template < typename DataType, typename KeyType, typename Comparator >
DataType Heap<DataType, KeyType, Comparator>::remove() throw (logic_error)
{
if (isEmpty() == true)
{
throw logic_error("Empty List");
}
size--;
DataType returnData = dataItems[0];
dataItems[0] = dataItems[size];
int index = 0;
while (index < size)
{
Comparator compare;
if ((index * 2) + 2 <= size)
{
if (compare(dataItems[index].getPriority(),dataItems[(index * 2) + 1].getPriority()) &&
compare(dataItems[index].getPriority(), dataItems[(index * 2) + 2].getPriority()))
{
return returnData;
}
else if (compare(dataItems[(index * 2) + 2].getPriority(),dataItems[(index * 2) + 1].getPriority()))
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[(index * 2) + 2];
dataItems[(index * 2) + 2] = temp;
index = (index * 2) + 2;
}
else
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[index + 1];
dataItems[(index * 2) + 1] = temp;
index = (index * 2) + 1;
}
}
else if ((index * 2) + 1 <= size)
{
if (compare(dataItems[(index * 2) + 1].getPriority(),
dataItems[index].getPriority()))
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[(index * 2) + 1];
dataItems[(index * 2) + 1] = temp;
index = (index * 2) + 1;
}
else
{
return returnData;
}
}
else
{
return returnData;
}
}
return returnData;
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType, KeyType, Comparator>::clear()
{
delete[]dataItems;
size = 0;
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType, KeyType, Comparator>::isEmpty() const
{
return (size == 0);
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType, KeyType, Comparator>::isFull() const
{
return (size == maxSize);
}
template<typename DataType, typename KeyType, typename Comparator>
void Heap<DataType, KeyType, Comparator>::writeLevels() const
{
}
template<typename DataType, typename KeyType, typename Comparator>
void Heap<DataType, KeyType, Comparator>::moveDown(DataType dataItem[], int root, int size)
{
}
#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<DataType,KeyType,Comparator>:: 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 << " ";
cout << endl;
for ( j = 0 ; j < size ; j++ )
cout << dataItems[j].getPriority() << " ";
cout << endl << endl;
showSubtree(0,0); // Output tree form
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType,KeyType,Comparator>:: 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 << " ";
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
}
}
---------------------------------------------------------------------------
//--------------------------------------------------------------------
//
// 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;
}
-----------------------------------------------------------------------------
//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 please use visual studio and make the program and all the function runs properly. Need this ASAP.
thank you.
----------------------------------------------------------------------------------------------------------
Implement the following two functions:
moveDown() - similar to remove() function, except that it doesn’t remove node and could work with a portion of the tree. (50 pts)
writeLevel() - output the data items in the level order. (50 pts
--------------------------------------------------------------------------------
//Heap.h
#ifndef HEAP_H
#define HEAP_H
#pragma warning( disable : 4290 )
#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
void moveDown(DataType dataItem[], int root, int size);
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<DataType, KeyType, Comparator>::Heap(int maxNumber = DEFAULT_MAX_HEAP_SIZE)
{
maxSize = maxNumber;
size = 0;
dataItems = new DataType[maxSize];
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>::Heap(const Heap& other)
{
*this = other;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>& Heap<DataType, KeyType, Comparator>::operator= (const Heap& other)
{
if (this == &other)
return *this;
if (isEmpty() == false)
clear();
size = other.size;
maxSize = other.maxSize;
for (inti = 0; i < size; i++)
dataItems[i] = other.dataItems[i];
return *this;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>::~Heap()
{
clear();
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType, KeyType, Comparator>::insert(const DataType &newDataItem)
throw (logic_error)
{
if (isFull() == false)
{
int index = size;
comparator compare;
dataItems[size] = newDataItem;
while (compare(dataItems[index].getPriority(), dataItems[(index - 1) / 2].getPriority()))
{
DataType data = dataItems[index];
dataItems[index] = dataItems[(inex - 1) / 2];
dataItems[(index - 1) / 2] = data;
index = (index - 1) / 2;
}
size++;
}
else
{
throw logic_error("Full List.")
}
}
?
template < typename DataType, typename KeyType, typename Comparator >
DataType Heap<DataType, KeyType, Comparator>::remove() throw (logic_error)
{
if (isEmpty() == true)
{
throw logic_error("Empty List");
}
size--;
DataType returnData = dataItems[0];
dataItems[0] = dataItems[size];
int index = 0;
while (index < size)
{
Comparator compare;
if ((index * 2) + 2 <= size)
{
if (compare(dataItems[index].getPriority(),dataItems[(index * 2) + 1].getPriority()) &&
compare(dataItems[index].getPriority(), dataItems[(index * 2) + 2].getPriority()))
{
return returnData;
}
else if (compare(dataItems[(index * 2) + 2].getPriority(),dataItems[(index * 2) + 1].getPriority()))
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[(index * 2) + 2];
dataItems[(index * 2) + 2] = temp;
index = (index * 2) + 2;
}
else
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[index + 1];
dataItems[(index * 2) + 1] = temp;
index = (index * 2) + 1;
}
}
else if ((index * 2) + 1 <= size)
{
if (compare(dataItems[(index * 2) + 1].getPriority(),
dataItems[index].getPriority()))
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[(index * 2) + 1];
dataItems[(index * 2) + 1] = temp;
index = (index * 2) + 1;
}
else
{
return returnData;
}
}
else
{
return returnData;
}
}
return returnData;
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType, KeyType, Comparator>::clear()
{
delete[]dataItems;
size = 0;
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType, KeyType, Comparator>::isEmpty() const
{
return (size == 0);
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType, KeyType, Comparator>::isFull() const
{
return (size == maxSize);
}
template<typename DataType, typename KeyType, typename Comparator>
void Heap<DataType, KeyType, Comparator>::writeLevels() const
{
}
template<typename DataType, typename KeyType, typename Comparator>
void Heap<DataType, KeyType, Comparator>::moveDown(DataType dataItem[], int root, int size)
{
}
#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<DataType,KeyType,Comparator>:: 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 << " ";
cout << endl;
for ( j = 0 ; j < size ; j++ )
cout << dataItems[j].getPriority() << " ";
cout << endl << endl;
showSubtree(0,0); // Output tree form
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType,KeyType,Comparator>:: 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 << " ";
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
}
}
---------------------------------------------------------------------------
//--------------------------------------------------------------------
//
// 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;
}
-----------------------------------------------------------------------------
//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
Explanation / Answer
#ifndef HEAP_H
#define HEAP_H
#pragma warning( disable : 4290 )
#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
void moveDown(DataType dataItem[], int root, int size);
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<DataType, KeyType, Comparator>::Heap(int maxNumber = DEFAULT_MAX_HEAP_SIZE)
{
maxSize = maxNumber;
size = 0;
dataItems = new DataType[maxSize];
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>::Heap(const Heap& other)
{
*this = other;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>& Heap<DataType, KeyType, Comparator>::operator= (const Heap& other)
{
if (this == &other)
return *this;
if (isEmpty() == false)
clear();
size = other.size;
maxSize = other.maxSize;
for (inti = 0; i < size; i++)
dataItems[i] = other.dataItems[i];
return *this;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType, KeyType, Comparator>::~Heap()
{
clear();
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType, KeyType, Comparator>::insert(const DataType &newDataItem)
throw (logic_error)
{
if (isFull() == false)
{
int index = size;
comparator compare;
dataItems[size] = newDataItem;
while (compare(dataItems[index].getPriority(), dataItems[(index - 1) / 2].getPriority()))
{
DataType data = dataItems[index];
dataItems[index] = dataItems[(inex - 1) / 2];
dataItems[(index - 1) / 2] = data;
index = (index - 1) / 2;
}
size++;
}
else
{
throw logic_error("Full List.")
}
}
?
template < typename DataType, typename KeyType, typename Comparator >
DataType Heap<DataType, KeyType, Comparator>::remove() throw (logic_error)
{
if (isEmpty() == true)
{
throw logic_error("Empty List");
}
size--;
DataType returnData = dataItems[0];
dataItems[0] = dataItems[size];
int index = 0;
while (index < size)
{
Comparator compare;
if ((index * 2) + 2 <= size)
{
if (compare(dataItems[index].getPriority(),dataItems[(index * 2) + 1].getPriority()) &&
compare(dataItems[index].getPriority(), dataItems[(index * 2) + 2].getPriority()))
{
return returnData;
}
else if (compare(dataItems[(index * 2) + 2].getPriority(),dataItems[(index * 2) + 1].getPriority()))
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[(index * 2) + 2];
dataItems[(index * 2) + 2] = temp;
index = (index * 2) + 2;
}
else
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[index + 1];
dataItems[(index * 2) + 1] = temp;
index = (index * 2) + 1;
}
}
else if ((index * 2) + 1 <= size)
{
if (compare(dataItems[(index * 2) + 1].getPriority(),
dataItems[index].getPriority()))
{
DataType temp = dataItems[index];
dataItems[index] = dataItems[(index * 2) + 1];
dataItems[(index * 2) + 1] = temp;
index = (index * 2) + 1;
}
else
{
return returnData;
}
}
else
{
return returnData;
}
}
return returnData;
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType, KeyType, Comparator>::clear()
{
delete[]dataItems;
size = 0;
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType, KeyType, Comparator>::isEmpty() const
{
return (size == 0);
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType, KeyType, Comparator>::isFull() const
{
return (size == maxSize);
}
template<typename DataType, typename KeyType, typename Comparator>
void Heap<DataType, KeyType, Comparator>::writeLevels() const
{
}
template<typename DataType, typename KeyType, typename Comparator>
void Heap<DataType, KeyType, Comparator>::moveDown(DataType dataItem[], int root, int size)
{
}
#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<DataType,KeyType,Comparator>:: 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 << " ";
cout << endl;
for ( j = 0 ; j < size ; j++ )
cout << dataItems[j].getPriority() << " ";
cout << endl << endl;
showSubtree(0,0); // Output tree form
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType,KeyType,Comparator>:: 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 << " ";
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
}
}
---------------------------------------------------------------------------
//--------------------------------------------------------------------
//
// 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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.