The code is having some errors. Unable to track the record of Left and Right Child. Need to create a Huffman tree from the min heap values. So that eaxh charachter can be used to obtain the encoded values of each letter. Data.txt is the file which consists of

data.txt

hello

welcome to my galaxy

#include #include #include #include #include using namespace std;

struct Item { char charachter; int frequency; Item* Left_Ch; Item* Right_Ch;

Item(char charachter, int frequency) { this->charachter = charachter; this->frequency = frequency; Left_Ch = nullptr; Right_Ch = nullptr; }

Item() { Left_Ch = nullptr; Right_Ch = nullptr; } };

class MinHeap { public: Item* arr; int total; int capacity;

void doubleCapacity() { Item* newArr = new Item[this->capacity * 2]; this->capacity *= 2;

for (int i = 0; i < this->total; i++) { newArr[i] = this->arr[i]; }

delete[]this->arr; this->arr = newArr; }

public: MinHeap() { this->arr = new Item[1]; this->total = 0; this->capacity = 1; }

MinHeap(int _capacity) { if (capacity > 0) { this->arr = new Item[_capacity]; this->total = 0; this->capacity = _capacity; } }

void insert(char charachter, int frequency) { if (this->total == this->capacity) this->doubleCapacity();

arr[this->total].charachter = charachter; arr[this->total].frequency = frequency;

shiftUp(this->total); this->total++; }

void shiftUp(int index) { int parent = (index - 1) / 2;

if (this->arr[index].charachter < this->arr[parent].charachter) { swap(this->arr[index], this->arr[parent]); }

else { return; }

if (parent > 0) { shiftUp(parent); } }

void deleteMin() { if (this->total == 0) { return; } swap(this->arr[total - 1], this->arr[0]); this->total--; shiftDown(0); }

void shiftDown(int index) { int Left_Ch = index * 2 + 1; int Right_Ch = index * 2 + 2; int min = index;

if (Left_Ch < this->total && this->arr[Left_Ch].charachter < this->arr[min].charachter) { min = Left_Ch; }

if (Right_Ch < this->total && this->arr[Right_Ch].charachter < this->arr[min].charachter) { min = Right_Ch; }

if (min == index) { return; }

swap(this->arr[min], this->arr[index]); shiftDown(min); }

void getMin(char& charachtery, int& val) { if (total > 0) { val = arr[0].frequency; charachtery = arr[0].charachter; } deleteMin(); }

~MinHeap() { delete[]this->arr; } };

class HuffMan { public: void build_Huffman(string fileName) {

string temp; unordered_map map;

ifstream infile; infile.open(fileName);

while (getline(infile, temp)) {

for (int i = 0; temp[i]; i++) {

if (map.find(temp[i]) == map.end()) { map.insert(make_pair(temp[i], 1)); }

else { map[temp[i]]++; } } }

MinHeap temp_heap; unordered_map::iterator i; for (i = map.begin(); i != map.end(); i++) { temp_heap.insert(i->first, i->second); }

//////////////////////////////////////////////////// // Create Huffman Tree // //////////////////////////////////////////////////// print_encoding(this->root,""); }

void print_encoding(Item* root, string code) { if (root == nullptr) { return; }

if (root->charachter != '@') { cout << root->charachter << " , " << root->frequency << " , " << code << endl; }

print_encoding(root->Left_Ch, code + "0"); print_encoding(root->Right_Ch, code + "1"); }

};

int main() {

HuffMan h; string file_name="data.txt"; h.build_Huffman(file_name);

system("pause"); return 0; }