PJ-利用霍夫曼樹進行資料壓縮

//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/%E8%B3%87%E8%A8%8A%E5%AD%B8%E7%A7%91%E8%83%BD%E5%8A%9B%E7%AB%B6%E8%B3%BD/108%E5%BD%B0%E9%9B%B2%E5%98%89/PJ-%E5%88%A9%E7%94%A8%E9%9C%8D%E5%A4%AB%E6%9B%BC%E6%A8%B9%E9%80%B2%E8%A1%8C%E8%B3%87%E6%96%99%E5%A3%93%E7%B8%AE.cpp

#include<iostream>
#include<map>
#include<string>
#include<unordered_set>
#include<queue>
using namespace std;
struct tree{
    int cnt=0;
    char elm='\0';
    tree* left=nullptr;
    tree* right=nullptr;
};
struct cmp{
    bool operator()(tree *a, tree *b){
        return a->cnt > b->cnt;
    }
};
map<char,string>huffman;
void dfs(tree *now,string code){
    if(now->elm!='\0'){
        huffman[now->elm]=code;
        return;
    }
    if(now->left){
        dfs(now->left,code+"0");
    }
    if(now->right){
        dfs(now->right,code+"1");
    }
}
int main(){
    string s;cin>>s;
    unordered_set<char>st;
    map<char,tree*>mp;
    for(char c:s){
        st.insert(c);
    }
    for(char c:st){
        mp[c]=new tree;
        mp[c]->elm=c;
    }
    for(char c:s){
        mp[c]->cnt++;
    }
    priority_queue<tree*,vector<tree*>,cmp>pq;
    for(char c:st){
        pq.push(mp[c]);
    }
    while(pq.size()>1){
        tree *a=pq.top(); pq.pop();
        tree *b=pq.top(); pq.pop();
        tree *c=new tree;
        c->cnt=a->cnt+b->cnt;
        c->left=a;
        c->right=b;
        pq.push(c);
    }
    dfs(pq.top(), "");
    int bits=0;
    for(char c:s){
        bits+=huffman[c].length();
    }
    int before=s.length()*8;
    cout<<before<<" "<<bits<<" "<<(before-bits)*100/before<<"%\n";
    return 0;
}