Huffman Encoding

huffman.cpp

#include <iostream>
#include <fstream>
#include <map>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

struct Node {
    shared_ptr<Node> left, right;
    char ch;
    int freq;
    Node(char ch, int freq, shared_ptr<Node> left = nullptr, shared_ptr<Node> right = nullptr)
        : left(left), right(right), ch(ch), freq(freq) {}
};

bool operator<(const shared_ptr<Node>& a, const shared_ptr<Node>& b) { return a->freq > b->freq; }

map <char, string> print_huffman_tree(shared_ptr<Node> root, string d) {
    map <char, string> mapping;
    if (root->left) {
        mapping.merge(print_huffman_tree(root->left, d + "0"));
    }
    if (root->right) {
        mapping.merge(print_huffman_tree(root->right, d + "1"));
    }
    if (!root->left && !root->right) mapping[root->ch] = d;
    return mapping;
}

int main() {
    map <char, int> cnt;
    priority_queue <shared_ptr<Node>> d;
    ifstream fin("file.txt");
    while (true) {
        char ch;
        fin >> ch;
        if (!fin) break;
        ++cnt[ch];
    }
    for (auto &&c : cnt) {
        d.push(make_shared<Node>(c.first, c.second));
    }
    while (d.size() > 1) {
        auto a = d.top(); d.pop();
        auto b = d.top(); d.pop();
        d.push(make_shared<Node>(0, a->freq + b->freq, a, b));
    }
    auto mapping = print_huffman_tree(d.top(), "");
    vector<pair<string, char>> dd;
    for (auto &&m : mapping){
        dd.push_back(make_pair(m.second, m.first));
    }
    sort(dd.begin(), dd.end(), [](auto &a, auto &b) {
        if (a.first.length() == b.first.length())
        return a.first < b.first; else return a.first.length() < b.first.length();
    });
    for (auto &&m : dd) {
        cout << m.first << " " << m.second << endl;
    }
    int sum = 0;
    for (auto &&c : cnt) {
        cout << c.first << " " << c.second << endl;
        sum += mapping[c.first].size() * c.second;
    }
    cout << sum << endl;
    return 0;
}