Question: Please use C++ language to answer the following question: Implement the following two functions to your heap structure: moveDown() - similar to remove() function, except
Please use C++ language to answer the following question:
Implement the following two functions to your heap structure:
moveDown() - similar to remove() function, except that it doesnt remove node and could work with a portion of the tree.
writeLevel() - output the data items in the level order.
//test11.cpp
//--------------------------------------------------------------------
//
// 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 < 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 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;
}
//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
// 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
// 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 } }
//Heap.cpp
#include "Heap.h"
template < typename DataType, typename KeyType, typename Comparator >
Heap
{
maxSize = maxNumber;
size = 0;
dataItems = new DataType[maxSize];
}
template < typename DataType, typename KeyType, typename Comparator >
Heap
{
*this = other;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap
{
if (this == &other)
return *this;
if (isEmpty() == false)
clear();
size = other.size;
maxSize = other.maxSize;
for (int i = 0; i < size; i++)
dataItems[i] = other.dataItems[i];
return *this;
}
template < typename DataType, typename KeyType, typename Comparator >
Heap
{
clear();
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap
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[(index - 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
{
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
{
delete[] dataItems;
size = 0;
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap
{
return (size == 0);
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap
{
return (size == maxSize);
}
#include "show11.cpp"
//Heap.h
//--------------------------------------------------------------------
//
// Laboratory 12 Heap.h
//
// Class declaration for the array implementation of the Heap ADataType
//
//--------------------------------------------------------------------
#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
//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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help