Huffman Coding in C++

Question

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;
}

Answer 1

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.

---

memory ownership is not easy to follow in your code

avoid using raw pointers. By using smart pointers ownership is always clear and you dont need to bother about where to delete.

struct Node
{
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;  // here it's clear that 'right' owns what it points to
    ...
}