Huffman coding

Optimized using priority queues haffman code .

1. Count the word frequency in the article
2. Use priority queues ( Pile up ) establish haffman Trees
3. Traverse Haffman The tree gets the of each character huffman code , Save in enc(unordered_map) in
4. Code the article
5. Use huffman Trees and haffman Code to decode .

establish huffman The time complexity of trees $O(ClogC)$ among C Is the number of word types .
The time complexity of coding $O(n)$, You just need to iterate through the string .
The time complexity of decoding $O(m)$, Just traverse the encoded string once .

huffman Coding is the basis of modern compression technology . I should write an I / O to test the compression of the file .
char yes 8 individual bit, and bit One bit in the array is 1 individual bit. So there must be compression effect .
The last file saved is haffman Tree and corresponding huaffman code . Read first when decoding haffmans Trees , Then decode the binary file .

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

// Encodes a URL to a shortened URL.
struct HuffmanTree {
    HuffmanTree *l, *r;
    int cnt;
    char ch;                              //  Word frequency and words 
    HuffmanTree(int cnt, char ch, HuffmanTree *l, HuffmanTree *r):cnt(cnt), ch(ch), l(l), r(r) {}
};
class cmp{
public:
    /* Node::priority  Big priority ,  Override less than sign  */
    bool operator () (HuffmanTree* &a, HuffmanTree* &b) const
    {
        return a->cnt > b->cnt;
    }
};

typedef pair<int, char>PR;
priority_queue<HuffmanTree*, vector<HuffmanTree*>, cmp>que, bakcup;
unordered_map<char, int>mp;

HuffmanTree* buildHuffman() {
    bakcup = que;
    while (!bakcup.empty()) {
        printf("%d %c\n", bakcup.top()->cnt, bakcup.top()->ch);
        bakcup.pop();
    }

    while (que.size() >= 2) {
        HuffmanTree* t1 = que.top(); que.pop();
        HuffmanTree* t2 = que.top(); que.pop();
        HuffmanTree *fa = new HuffmanTree(t1->cnt + t2->cnt, '#', t1, t2);
        que.push(fa);
    }
    return que.top();
}
HuffmanTree *root;
unordered_map<char, string>enc;
void travel(HuffmanTree *root, string s) {              //  Get the of each node huffman code 
    if (root == NULL) return ;
    //  leaf node ,  Statistical coding 
    if (root->l == NULL && root->r == NULL) {
        cout << root->ch << " " << s << endl;
        enc[root->ch] = s;
        return ;
    }
    travel(root->l, s + '0');
    travel(root->r, s + '1');
}
string encode(string longUrl) {
    for (char ch : longUrl) {
        mp[ch]++;
    }
    for (auto [ch, cnt] : mp) {
        que.push(new HuffmanTree(cnt, ch, NULL, NULL)); //  It's storing the hands .
    }

    root = buildHuffman();
    travel(root, "");                                   //  Traverse haffman Tree acquisition Huffman code 
    string ans;
    for (char ch : longUrl) {
        ans += enc[ch];
    }
    return ans;
}


string treeDecode(HuffmanTree *root, int &cur, string &s) {
    if (root == NULL) return "";
    if (root->l == NULL && root->r == NULL) {
        string ans = "";
        ans += root->ch;
        return ans;
    }
    cur++;
    if (s[cur] == '0') return treeDecode(root->l, cur, s);
    else return treeDecode(root->r, cur, s);
}
// Decodes a shortened URL to its original URL.
string decode(string shortUrl) {
    int cur = -1;
    string ans;
    int n = shortUrl.size();
    for (cur; cur < n - 1;) {
        printf("cur = %d\n", cur);
        string s = treeDecode(root, cur, shortUrl);
        cout << s << endl;
        ans += s;
    }
    return ans;
}

int main() {

    string s = "aaabbc";
    s = encode(s);
    cout << s << endl;
    cout << decode(s) << endl;
}