Entropy

哈夫曼树和哈夫曼编码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
  //           数据类型 容器   从小到大排列   
  priority_queue <int, vector<int>, greater<int> > q;  //小堆顶，堆顶最小
  string s;
  while(getline(cin, s) && s != "END"){  //从输入流读取一行赋给s
    sort(s.begin(), s.end());            // 升序排列
    int num = 1;                    //一种字符出现的次数
    for(int i = 1; i <= s.length(); i++){
      if(s[i] != s[i-1]){ q.push(num);  num = 1;}  //队尾压入新字符
      else num++;   //相同字符 num++
    }
    int ans = 0;
    if(q.size() == 1)              //题目的一个坑：只有一种字符的情况
    ans = s.length();   
    while(q.size() > 1){           //最后一次合并不用加到ans里    
      int a = q.top(); q.pop();    //贪心：取出频次最少的两个     
      int b = q.top(); q.pop();
      q.push(a+b);                 //把两个最小的合并成新的结点，重新放进队列
      ans += a+b;                  //一种字符进几次队列，就累加几次。
                                   //进一次队列，表示它在二叉树上深了一层，编码长度加1
    }
    q.pop();
    printf("%d %d %.1f\n",s.length()*8,ans,(double)s.length()*8/(double)ans);
  }
  return 0;
}

笔记：哈夫曼数是带权二叉树的最优解，哈夫曼编码是在保证解码还原正确的基础上的最小长度，哈夫曼编码将权值比较高的元素编码长度设置的小，以节省更多的空间