Skip to main content
Question Protected by Jamal
Asking for code to be written is off-topic for Code Review
Source Link
200_success
  • 145.6k
  • 22
  • 191
  • 481

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. And if possible please write modified code because I am learning to use STL.

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. And if possible please write modified code because I am learning to use STL.

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.

Source Link
coder
  • 2.5k
  • 4
  • 33
  • 60

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. And if possible please write modified code because I am learning to use STL.

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