read the description

Assignment

Your assignment is to implement the SkewHeap class which implements a skew heap that can store both strings and integers using the tagged union construction. In addition, SkewHeap allows the user to determine how priorities are computed by passing a pointer to a prioritization function to the constructor. In addition, the user can change the prioritization function of an existing skew heap using a setter method, and the class will rebuild the heap using the new prioritization.

You must complete an additional class that uses SkewHeap, the TypedHeap class. The TypedHeap class maintains two skew heaps: an integer heap and a string heap. The user provides a vector of strings to insert, which are processed as follows:

• If the string represents an integer (consists only of decimal digits), then convert it to an integer and insert it into the integer skew heap.
• If the string does not represent an integer (contains non-digit characters), insert it into the string skew heap.

In addition, the user may request, through a combineHeaps() method, that the string and integer heaps be merged into a third “total” heap. Functions to change the priority function and to dump the skew heaps must also be implemented.

Although several test programs are provided, you are responsible for thoroughly testing your program. It is particularly important that your code run without segmentation faults, memory leaks, or memory errors. Memory leaks are considered as bad as segmentation fault since many segmentation faults are caused by poorly written destructors. A program with a poorly written destructor might avoid some segmentation faults but will leak memory horribly. Memory leaks will incur a penalty similar to that of a segmentation fault.

Following is a list of member functions that must be implemented. Function prototypes are provided in SkewHeap.h and TypedHeap.h. You will need to create the implementation files, SkewHeap.cpp and TypedHeap.cpp.

Public Methods in SkewHeap

• A constructor with the signature:
• SkewHeap::SkewHeap( pri_fn pri ) ;
• A copy constructor with the signature:
• SkewHeap::SkewHeap( const SkewHeap& rhs ) ;
• A destructor with the signature:
• SkewHeap::~SkewHeap() ;
• An overloaded assignment operator with the signature:
• const SkewHeap& SkewHeap::operator=( const SkewHeap& rhs ) ;
• A function that returns a pointer to the current priority function:
• bool SkewHeap::getPriFn() const;
• A function that sets the priority function:
• int SkewHeap::setPriFn( pri_fn pri ) ;
• A function that returns “true” if the skew heap is emtpy; false otherwise:
• bool SkewHeap::empty() const ;
• A function that inserts a string value into the skew heap:
• void SkewHeap::insert( string data ) ;
• A function that inserts an integer value into the skew heap:
• void SkewHeap::insert( int data ) ;
• A function to access the highest priority element of the skew heap:
• Node* SkewHeap::front() const;
• A function to remove the highest priority element from the skew heap:
• void SkewHeap::removeTop() ;
• A function to merge two skew heaps:
• void SkewHeap::skewHeapMerge( SkewHeap &sh ) ;
• A member function inorder() that performs an inorder traversal and prints the data at each node:
• void SkewHeap::inorder() const ;
• A function dump() that prints all the data in the skew heap:
• void SkewHeap::dump() const ;

The default constructor must create an empty SkewHeap object with the given priority function. The skew heap must be ready for heap operations; even an empty tree should behave properly when its methods are called.

The copy constructor must make a deep copy and create a new object that has its own allocated memory.

The destructor must completely free all memory allocated for the object. (Use valgrind on GL to check for memory leaks.)

The assignment operator must deallocate memory used by the host object and then make deep copy of rhs.

Changing the priority function will typically invalidate the current skew heap. This function must rebuild the heap using the new priority function to ensure that the heap is still valid.

Returns a pointer to the highest priority node in the skew heap. Should return nullptr if the heap is emtpy.

Should do nothing if the skew heap is empty.

When the function completes, *this should contain the merged heap and sh should be empty.

The inorder() methods visits each node using an inorder traversal and prints out the data. It also prints an open parenthesis before visiting the left subtree and a close parenthesis after visiting the right subtree. Nothing is printed when inorder() is called on an empty tree, not even parentheses. This function may be used for grading and is useful for debugging.

See the sample output files for an example of what should be printed by dump().

Public Methods in TypedHeap

• A constructor with the signature:
• TypedHeap::TypedHeap( pri_fn pri ) ;
• An insertion function with the signature:
• TypedHeap::insertToHeaps( vector<string> vec ) ;
• An function to combine the integer and string heaps:
• TypedHeap::combineHeaps() ;
• An function to print the contents of the three heaps:
• TypedHeap::printHeaps() const ;
• A function to change the priority function for all three skew heaps:
• TypedHeap::changePriority( pri_fn pri ) ;

The default constructor must create three empty TypedHeaps, one to hold integer data, one to hold string data, and another to hold the combined skew heaps (when requestd by calling combineHeaps()). Each skew heap must be ready for heap operations; even an empty heap should behave properly when its methods are called.

The input is a vector of strings. For each string in the vector, the function must determine whether it represents an integer (consists entirely of decimal digits, possibly with leading or trailing spaces) and, if so, insert it into the integer heap; if it does not represent an integer, insert it into the string heap.

After combineHeaps() is called, the merged heap will be in totalHeap and the string and integer heaps will be empty.

See the sample output files for examples of what should be printed by this function.

This function must change the priority function for each of the three skew heaps, causing the heaps to be re-built with the new prioritization.