WRITE USING C++ PLEASE

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:

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.

CODE GIVEN:

main.cpp

#include #include "huffman_tree.h" using namespace std;

int main(int argc, char** argv) { // Create a HuffmanTree object and read the input messages into the // HuffmanTree construct function. Next, print the encoded message. // Finally, destruct the huffman tree and move on to the next test case. }

huffman_tree.cpp

#include #include "huffman_tree.h" #include "min_heap.h" using namespace std;

void HuffmanTree::construct(const string message) { this->message = message;

// Count the frequency of each letter in message // e.g. // message == "aaabbccccdd" // frequencies == {a:3, b:2, c:4, d:2} map frequency_map; for (int i = 0; i < message.length(); ++i) { if (frequency_map.find(message[i]) != frequency_map.end()) ++frequency_map[message[i]]; else frequency_map[message[i]] = 1; }

// Create HuffmanNode for each unique letter in message // and organize nodes into a min heap // e.g. // heap == // {b:2} // / \ // {d:2} {a:3} // / \ / \ // {c:4} MinHeap heap; map::iterator it = frequency_map.begin(); for (; it != frequency_map.end(); ++it) { HuffmanNode* node = new HuffmanNode( it->first, it->second ); heap.insert(node, it->second); }

// Combine nodes with smallest frequency and insert // back into heap until heap size == 1. Along the way, // create binary tree out of combined nodes. // e.g. // (1) // {b:2} == heap.extract_min() // {d:2} == heap.extract_min() // parent == // {*:4} // / \ // {b:2} {d:2} // // heap == // {a:3} // / \ // {c:4} {*:4} // // (2) // {a:3} == heap.extract_min() // {c:4} == heap.extract_min() // parent == // {*:7} // / \ // {a:3} {*:4} // // heap == // {c:4} // / // {*:7} // // (3) // {*:4} == heap.extract_min() // {*:7} == heap.extract_min() // parent == // {*:11} // / \ // {c:4} {*:7} // / \ // {a:3} {*:4} // / \ // {b:2} {d:2} // // heap == {*:11} while (heap.size() > 1) { HuffmanNode *left, *right;

left = heap.extract_min(); right = heap.extract_min();

HuffmanNode *parent = new HuffmanNode( left->frequency + right->frequency );

parent->left = left; parent->right = right;

heap.insert(parent, parent->frequency); }

// Get root of huffman tree. e.g. {*:11} this->root = heap.peek(); }

void HuffmanTree::print() const { // need to implement this function // Print the Huffman encoding of this->message. // Append 0 to a character's encoding if moving left in Huffman tree. // Append 1 to a character's encoding if moving right in Huffman tree.

// Remember, your Huffman tree is pointed at by this->root, so start your // character searches from there.

// Also, feel free to add a print helper function.

}

huffman_tree.h

#ifndef HUFFMAN_TREE_H #define HUFFMAN_TREE_H

#include #include

struct HuffmanNode { HuffmanNode(char character, int frequency) : character(character), frequency(frequency), left(NULL), right(NULL) {}

HuffmanNode(int frequency) : character('*'), frequency(frequency), left(NULL), right(NULL) {}

~HuffmanNode() { delete left; delete right; left = right = NULL; } char character; int frequency; HuffmanNode *left, *right; };

class HuffmanTree { public: HuffmanTree() : root(NULL), message("") {} ~HuffmanTree() {delete this->root;}

void construct(const string message); void destruct() {delete this->root; this->root=NULL; message="";} void print() const;

private:

HuffmanNode *root; string message; };

#endif

min_heap.h

#include #include using namespace std;

template struct HeapNode { HeapNode(const T data, const int key) : data(data), key(key) {} bool operator<(const HeapNode& rhs) {return this->key < rhs.key;} bool operator<=(const HeapNode& rhs) {return this->key <= rhs.key;}

T data; int key; };

template class MinHeap { public: MinHeap() {} ~MinHeap() {}

void insert(const T data, const int key); T extract_min(); T peek() const {T data; return data;}; // need to implement this function

int size() const { return 0;}; // need to implement this function

private: vector > heap; };

makefile

all: g++ huffman_tree.cpp main.cpp

clean: rm a.out