贪心算法：哈夫曼编码（HDU1053 2527题）

今天的主题就是大名鼎鼎的哈夫曼编码了。首先我们通过杭电的一道题来引入主题。
先给出传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2527

HDU2527

Safe Or Unsafe
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3428 Accepted Submission(s): 1402

Problem Description
Javac++ 一天在看计算机的书籍的时候，看到了一个有趣的东西！每一串字符都可以被编码成一些数字来储存信息，但是不同的编码方式得到的储存空间是不一样的！并且当储存空间大于一定的值的时候是不安全的！所以Javac++ 就想是否有一种方式是可以得到字符编码最小的空间值！显然这是可以的，因为书上有这一块内容—哈夫曼编码(Huffman Coding)；一个字母的权值等于该字母在字符串中出现的频率。所以Javac++ 想让你帮忙，给你安全数值和一串字符串，并让你判断这个字符串是否是安全的？

Input
输入有多组case，首先是一个数字n表示有n组数据，然后每一组数据是有一个数值m(integer)，和一串字符串没有空格只有包含小写字母组成！

Output
如果字符串的编码值小于等于给定的值则输出yes，否则输出no。

Sample Input
2
12
helloworld
66
ithinkyoucandoit

Sample Output
no
yes

首先我们可以看到这道题的题意应该比较清晰了，就是将字符串进行编码，转换为2进制的一串数字。那么如何编码呢，那我们就要引入哈夫曼编码了，在此之前我先引出哈夫曼树的概念。

哈夫曼树

首先我们假设我们的字符串是“AAABCCD”，那么假设我们有下面这一棵树的结构，每次我们从树根向下走，想左就是0，向右就是1，这样我们就可以对字符进行二进制表示了。


我们就可以轻易地得到这个字符串的二进制编码“111111111101101100”

而且你可以观察出一个现象，这个字符串不会产生歧义，不会出现一个二进制串对应好多种情况的问题，这是为什么呢？因为哈夫曼树的所有字符的位置必须是叶子节点（没有子节点的节点，最后的节点），由于每个叶子节点的路径都是独一无二的，所以我们会发现编码也不会引起歧义，不会出现像A为“111”而B是“11”这种无法判断的情况。

还有一个特别有意思的情况，我们会改变一下哈夫曼树的样子，就像下图这样

我们可以看到这时二进制变成了“00000001101011”，明显比第一次的短吧，在实际应用中，如果数据量很大，省下一个比特可能都会带来很大的变化。

最后我们再看看下图

这次二进制编码变成了“0001101010111”，很明显这次的最短吧。经过三张图片的比对你会发现，只要把出现次数越多的字母放在上面，把出现次数越少的字母放在下面，这样我们编码出来的二进制串就会是最短长度。

在很多的实际应用中，很多哈夫曼编码的程序就会根据字符出现的次数来动态创建哈夫曼树，这样可以使二进制码最短，然后解码方根据这个哈夫曼树和二进制码也可以最快地得出字符串。

那么HDU2527就是要我们根据这个字符串找到最短的二进制码，换言之就是找到最好的哈夫曼树，那么我们该怎么做呢？

最优哈夫曼树

首先我们需要这样几个步骤：

• 1.按出现频率排队，出现次数越多的字符排在越后面。
• 2.把两个队伍最前面的节点（就是次数最少的两个）相加，然后在两个节点头上生成一个父节点，并把父节点的出现次数设置为两个子节点出现次数的总和。
• 3.再次排序，始终次数较低的节点放在左边，然后继续第二步，直到最后只剩一个节点跳出循环。
• 4.最后剩下的节点就是这棵最优哈夫曼树的根节点。

下面是是图示





所以我们会发现其实最麻烦的还是一直要排序这一步，所以我们采用优先队列，而且是从小到大的优先队列，就可以轻松搞定这个排序的任务，然后就是算出最小长度，我们可以发现一个字符所占的长度是由它的出现次数×字符所占的位数（就是深度）决定的，因为跟深度有关，我们又要将树慢慢地变深，所以我们可不可以直接每一步合并的时候将合并后的值sum直接加到答案ans中去，需要合并三次的节点就会重复加3次，正好就是深度，所以就有了下面的代码：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int ch[30];

int main(){
    int T;
    while(cin>>T){
        int n;
        string s;
        while(T--){
            cin>>n>>s;
            memset(ch,0,sizeof(ch));
            for(int i=0;i<s.length();i++)
                ch[s[i]-'a']++;
            priority_queue<int,vector<int>,greater<int> > que;
            for(int i=0;i<30;i++)
                if(ch[i])
                    que.push(ch[i]);
            int flag=1,sum=0,ans=0;
            if(que.size()==1){
                flag=0;
                ans=que.size();
            }
            while(que.size()>1&&flag){
                int t1=que.top();que.pop();
                int t2=que.top();que.pop();
                sum=t1+t2;
                ans+=sum;
                que.push(sum);
            }
            //cout << ans << endl;
            if(ans<n)
                cout << "yes" << endl;
            else
                cout << "no" << endl;
        }
    }
    return 0;
}

HDU1053题

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1053
题目是英文的，请大家点击链接自行查看。

这道题也是换汤不换药，也用上面的思路做就可以了，无非就是多了个除一下然后保留小数的操作罢了
下面是AC代码：

#include <iostream>
#include <cstring>
#include <queue>
#include <iomanip>
using namespace std;
int ch[30];

int main(){
    string s;
    while(cin>>s&&s!="END"){
        memset(ch,0,sizeof(ch));
        for(int i=0;i<s.length();i++) {
            if (s[i] == '_')
                s[i]='Z'+1;
            ch[s[i]-'A']++;
        }
        priority_queue<int,vector<int>,greater<int> > que;
        for(int i=0;i<30;i++)
            if(ch[i])
                que.push(ch[i]);
        int ans=0,sum=0;
        int flag=1;
        if(que.size()==1) {
            ans = que.top();
            flag = 0;
        }
        while(que.size()>1&&flag){
            int t1=que.top();que.pop();
            int t2=que.top();que.pop();
            sum=t1+t2;
            ans+=sum;
            que.push(sum);
        }
        cout << s.length()*8 << ' ' << ans << ' ';
        cout << fixed << setprecision(1) << (double)(s.length()*8)/ans << endl;
    }
    return 0;
}

ok，总算是写完了。。哈哈。