# Huffman Coding in C++

I have written this code after studying from Introduction to Algorithm and from GeeksForGeeks. I know there is a lot to improve because I don't know much C++11. Please help me to improve this code.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

class HuffmanCodes
{
struct Node
{
char data;
size_t freq;
Node* left;
Node* right;
Node(char data, size_t freq) : data(data),
freq(freq),
left(nullptr),
right(nullptr)
{}
~Node()
{
delete left;
delete right;
}
};

struct compare
{
bool operator()(Node* l, Node* r)
{
return (l->freq > r->freq);
}
};

Node* top;

void printCode(Node* root, std::string str)
{
if(root == nullptr)
return;

if(root->data == '$') { printCode(root->left, str + "0"); printCode(root->right, str + "1"); } if(root->data != '$')
{
std::cout << root->data << " : " << str << "\n";
printCode(root->left, str + "0");
printCode(root->right, str + "1");
}
}

public:
HuffmanCodes() {};
~HuffmanCodes()
{
delete top;
}
void GenerateCode(std::vector<char>& data, std::vector<size_t>& freq, size_t size)
{
Node* left;
Node* right;
std::priority_queue<Node*, std::vector<Node*>, compare > minHeap;

for(size_t i = 0; i < size; ++i)
{
minHeap.push(new Node(data[i], freq[i]));
}

while(minHeap.size() != 1)
{
left = minHeap.top();
minHeap.pop();

right = minHeap.top();
minHeap.pop();

top = new Node('\$', left->freq + right->freq);
top->left  = left;
top->right = right;
minHeap.push(top);
}
printCode(minHeap.top(), "");
}
};

int main()
{
HuffmanCodes set1;
std::vector<char> data({'d', 'e', 'b', 'c', 'a', 'f'});
std::vector<size_t> freq({16, 9, 13, 12, 45, 5});
size_t size = data.size();
set1.GenerateCode(data, freq, size);

return 0;
}

• Aside from everything else: consistent indentation, please!
– muru
Commented Sep 9, 2017 at 13:05

When you declare a class, initialize all member variables

char data = '\0';
size_t freq = 0;
...


(depending on your compiler you may need to do that in the constructor instead)

especially pointers, since a delete on an uninitialized pointer is undefined behavior but a delete on a nullptr is OK (NOP).

void GenerateCode(std::vector<char>& data, std::vector<size_t>& freq, size_t size)


is your intention to modify 'data'? if not, then write const in front

void GenerateCode(const std::vector<char>& data, std::vector<size_t>& freq)


why do you pass 'size'? 'data' already has a size: data.size()

you have an unitialized member variable called 'top', you use it in GenerateCode and it will be set there, but if you never call GenerateCode, just a simple class declaration will invoke undefined behavior since delete top is called in HuffManCodes destructor.

struct Node