Question
Task For this project, you have been provided an implementation of the Huffman tree construction algorithm (DO NOT modify this code. It is possible to
Task
For this project, you have been provided an implementation of the Huffman tree construction algorithm (DO NOT modify this code. It is possible to construct multiple Huffman trees with the same message if numerous characters in the message share the same frequency value. The construct function that I set up ensures that your Huffman tree will produce results consistent with the test cases used for grading). This algorithm utilizes a templated min heap class that you must implement. You must also implement a function that prints the Huffman encoding of message using the Huffman tree constructed from the same message. Specifically, you must implement the following functions:
void MinHeap::insert(const T data, const int key) :
Insert the provided user data into the min heap using the provided key to make comparisons with the other elements in the min heap. To ensure that your min heap produces consistent results, stop bubbling up a child node if it shares the same key value as its parent node.
T MinHeap::extract min() :
Remove from the min heap the element with the smallest key value and return its data. If you come across two sibling nodes that share the same key value while sifting down a parent node with a larger key value, then you should swap the parent node with the left child to ensure that your min heap produces consistent results.
T MinHeap::peek() const :
Retrieve the minimum element in the min heap and return its data to the user. Do not remove this element from the min heap in this function.
void MinHeap::size() const :
Return the size of the min heap.
void HuffmanTree::print() const :
Print the Huffman encoding of the member variable message assigned in the construct function.
To ensure that you always produce a consistent output, DO NOT modify the completed code in the HuffmanTree class. You may however add print helper functions if you feel it necessary.
Input
Input is read from the keyboard. The first line of the input will be an integer t > 0 that indicates the number of test cases. Each test case will contain a message on a single line to be processed by the Huffman tree construct function. Each message will contain at least 2 characters.
Output
For each test case, print Test Case: followed by the test case number on one line. On another line, print the Huffman encoding of the input message. Separate the individual character encodings by a space.
Sample Test Cases
Use input redirection to redirect commands written in a file to the standard input, e.g. $ ./a.out < input1.dat.
Input 1
3
opossum
hello world
message
Output 1
Test Case: 1
11 00 11 10 10 011 010
Test Case: 2
010 011 10 10 00 1100 1101 00 1110 10 1111
Test Case: 3
011 10 11 11 010 00 10
Timing Analysis
At the top of your main file, in comments, write the time complexity of constructing a Huffman tree with a min heap in terms of the number of characters in the input message, which you can denote as n. Also consider the time complexity of constructing a Huffman tree without a min heap. Specifically, what running time can you expect if you use a linear search to find minimum frequencies. Write these time complexities using Big-O notation.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started