fork download
copy 
  1. #include <iostream>
  2. #include <string>	
  3. #include <fstream>
  4. #include <sstream>
  5. #include <vector>       
  6. #include <algorithm>
  7. #include <memory>
  8. #include <iomanip>
  9. #include <cassert>
  10.  
  11. struct node;
  12. using node_handle = std::unique_ptr<node>;
  13.  
  14. struct node
  15. {
  16.     char data;
  17.     std::size_t frequency;
  18.  
  19.     node_handle left;
  20.     node_handle right;
  21.  
  22.     node(std::size_t freq) : data('\0'), frequency(freq) {}
  23.     node(char ch, std::size_t freq) : data(ch), frequency(freq) {}
  24.  
  25.     bool operator<(const node& n) { return frequency < n.frequency; }
  26.  
  27.     bool isLeaf() const { return left == nullptr && right == nullptr;}
  28. };
  29.  
  30. std::vector<node_handle> extractHuffmanData(std::istream& is)
  31. {
  32.     std::vector<node_handle> data;
  33.  
  34.     std::size_t frequency;
  35.     char ch;
  36.  
  37.     while (is >> ch >> frequency)
  38.         data.emplace_back(new node(ch, frequency));
  39.  
  40.     return data;
  41. }
  42.  
  43. node_handle buildHuffmanTree(std::vector<node_handle> data)
  44. {
  45.     assert(data.size() > 0);
  46.  
  47.     auto comp = [](const node_handle& a, const node_handle& b)    
  48.     { 
  49.         return *a < *b; 
  50.     };
  51.  
  52.     std::sort(data.begin(), data.end(), comp);
  53.  
  54.     while (data.size() > 1)
  55.     {
  56.         node_handle a(data[0].release());
  57.         node_handle b(data[1].release());
  58.         data.erase(data.begin(), data.begin() + 2);
  59.  
  60.         node_handle parent(new node(a->frequency + b->frequency));
  61.         parent->left.swap(a);
  62.         parent->right.swap(b);
  63.  
  64.         auto pos = std::lower_bound(data.begin(), data.end(), parent, comp);
  65.         data.emplace(pos, parent.release());
  66.     }
  67.  
  68.     return node_handle(data.back().release());
  69. }
  70.  
  71. void print(const node_handle& node, std::size_t indent_level=0)
  72. {
  73.     if (node == nullptr)
  74.         return;
  75.  
  76.     const size_t indent_width = 2;
  77.     std::cout << std::setw(indent_width * indent_level) << "";
  78.     std::cout << node->frequency;
  79.  
  80.     if (node->isLeaf())
  81.         std::cout << " - " << node->data << '\n';
  82.     else
  83.     {
  84.         std::cout << '\n';
  85.         print(node->left, indent_level + 1);
  86.         print(node->right, indent_level + 1);
  87.     }
  88. }
  89.  
  90. int main()
  91. {
  92.     std::istringstream is
  93.     {
  94.         "a 119\n"
  95.         "b 20\n"
  96.         "c 44\n"
  97.         "d 127\n"
  98.     };
  99.  
  100.     auto huffmanData = extractHuffmanData(is);
  101.     auto huffmanTree = buildHuffmanTree(std::move(huffmanData));
  102.  
  103.     print(huffmanTree);
  104. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
310
  127 - d
  183
    64
      20 - b
      44 - c
    119 - a
https://ideone.com/Bqi35e
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!