哈夫曼编码是一种用于数据压缩的编码方式，它使用变长编码来表示数据源中的符号。频率较高的符号用较短的编码，频率较低的符号用较长的编码，从而达到减少总编码长度的目的。

编码过程

例子：

对字母进行哈夫曼编码时的性质：

1.每个字母对应元素叶节点的值是该字母出现的次数

2.出现次数越多的字符编码越短

3.不出现歧义的情况下编出来的码长度最短

4.编码结果不唯一，字母编出来的码可能不一样，但是长度肯定一样

参考b站视频：哈夫曼树和哈夫曼编码, 看完秒懂！

不会出现歧义原因：不存在任意一个元素节点出现在另一个元素节点的路径中

应用： 压缩文件

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
#include <vector>

using namespace std;

struct Node {
    char ch;
    int freq;
    Node *left, *right;

    Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}

    // For priority_queue to work, we need to define the comparison operator.
    bool operator<(const Node &node) const {
        return this->freq > node.freq;
    }
};

// Function to build Huffman Tree
Node* buildHuffmanTree(string text) {
    unordered_map<char, int> frequency;
    for (char ch : text)
        ++frequency[ch];

    priority_queue<Node, vector<Node>, greater<Node>> minHeap;
    for (auto pair : frequency)
        minHeap.push(*new Node(pair.first, pair.second));

    while (minHeap.size() != 1) {
        Node *left = new Node(minHeap.top()); minHeap.pop();
        Node *right = new Node(minHeap.top()); minHeap.pop();

        Node *top = new Node('\0', left->freq + right->freq);
        top->left = left;
        top->right = right;
        minHeap.push(*top);
    }

    return new Node(minHeap.top());
}

// Traverse the Huffman Tree and store Huffman Codes in a map
void encodeMap(Node* root, string str, unordered_map<char, string> &huffmanCode) {
    if (!root)
        return;

    if (!root->left && !root->right)
        huffmanCode[root->ch] = str;

    encodeMap(root->left, str + "0", huffmanCode);
    encodeMap(root->right, str + "1", huffmanCode);
}

// Function to print huffman codes
void printCodes(unordered_map<char, string> &huffmanCode) {
    cout << "Character" << "\t" << "Frequency" << "\t" << "Code" << endl;
    for (auto pair : huffmanCode)
        cout << pair.first << "\t\t" << huffmanCode[pair.first].size() << "\t\t" << pair.second << endl;
}

// Encode the input text using the generated Huffman codes
string encode(const string &text, unordered_map<char, string> &huffmanCode) {
    string encodedString = "";
    for (char ch : text)
        encodedString += huffmanCode[ch];
    return encodedString;
}

int main() {
    string text = "this is an example for huffman encoding";
    
    Node* root = buildHuffmanTree(text);
    unordered_map<char, string> huffmanCode;
    encodeMap(root, "", huffmanCode);

    printCodes(huffmanCode);

    string encodedString = encode(text, huffmanCode);
    cout << "Encoded string: " << encodedString << endl;

    return 0;
}

这段代码首先统计了输入字符串中每个字符出现的频率，然后创建了一个最小堆（priority_queue），其中存储的是由字符及其频率组成的节点。通过不断地从堆中取出两个频率最低的节点并合并成一个新的节点，最终构建出哈夫曼树。之后，通过遍历哈夫曼树生成每个字符对应的编码，并将这些编码存储在一个映射表中。最后，根据这个映射表对原始字符串进行编码。

请注意，这个简单的实现并没有包括解码过程、内存释放或者处理可能的异常情况。在实际应用中，你还需要考虑这些问题。此外，由于C++标准库中没有直接支持优先队列元素为自定义类型的比较，我们重载了小于操作符以适应 priority_queue 的需求。