基本概念

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

• 带权路径长度：

  

  题目

  哈夫曼编码

  注意考虑树只有一个点的情况 ```cpp

  include

  include

  include

  include

  include

  include

using namespace std;

const int N = 1010;

char s[N]; unordered_map rec; // 记录字母出现次数

int main() {

#ifdef SUBMIT
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
long _begin_time = clock();
#endif
while (scanf("%s", s), strcmp(s, "END") != 0) {
    int len = strlen(s);
    rec.clear();    // 记得清空
    for (int i = 0; i < len; i++) {
        rec[s[i]]++;
    }
    priority_queue<int, vector<int>, greater<int>> heap;    // 优先队列没有clear方法
    for (auto it = rec.begin(); it != rec.end(); it++) {
        heap.push(it->second);
        // cout << (double)it->second / len << ' ';
    }
    // cout << endl;
    int avg = 0;
    if (heap.size() == 1) {    // 注意，只有一个点时，带权路径长度就是那个点的权值
        avg = heap.top();
    }
    while (heap.size() > 1) {    // 至少有两个点才能合并
        double a1 = heap.top(); heap.pop();
        double a2 = heap.top(); heap.pop();
        avg += a1 + a2;
        heap.push(a1 + a2);
    }
    // cout << avg << endl;
    int ori = len * 8;
    printf("%d %d %.1lf\n", ori, avg, (double)ori / avg);
}    
#ifdef SUBMIT
long _end_time = clock();
printf("\n\ntime = %ld ms", _end_time - _begin_time);
#endif
return 0;

} ```