机智零崎不会没梗Ⅱ (哈夫曼编码、优先队列)

题目描述

你满心欢喜的召唤出了外星生物，以为可以变身超人拥有强大力量战胜一切怪兽，然而面对着身前高大的外星生物你一脸茫然，因为，你懂M78星云语吗？不过不用担心，因为零崎非常机智，他给出了关键性的提示：“讲道理，日语可是全宇宙通用语，所以为什么不试试和外星人讲日语呢？”

不过现在外星生物说的话都是“!@#$%^&%#%I&!……”这样的东西，你要怎么转换成日语呢？

作位全宇宙通用的日语，自然有一套万能的转换算法，那就是Huffman编码转换！当然了这肯定不是普通的Huffman编码转换，而是根据不同的编码长度转换为不同的假名。

输入

第一行为一个整数t，接下来t行数据。1<=t<=100

每组输入数据为一个外星语字符串，为了表示方便，暂时使用大小写英文字母代替外星字母。字符串长度不超过2000

输出

对于每组数据，输出对应的二进制Huffman编码总长度

输入样例

2
abababac
abcdefg

输出样例

12
20题目来源：http://biancheng.love/contest/23/problem/D/index解题思路:在前面的哈夫曼树构造以及哈夫曼编码和解码时，已经讲述了哈夫曼编码的方式。现在我们需要得到哈夫曼编码的长度。回忆一下在解码过程中的算法，如果是0向左搜索，如果是1向右搜索。因此一个字符在一个构造好的哈夫曼树中都是居于叶子结点。意思就是树的各个分叉的最低端。因此每个字符的长度也就是该字符在哈夫曼树中的深度。希望能够理解这一点。在明白字符长度就是字符深度之后开始重新分析一下哈夫曼的树的构造过程。哈夫曼树的建立时通过对每个字符出现频率的统计来设计的，不同的出现频率会对应不同的深度也就是不同的长度。建立过程如下：1、取出频率最小的两个数，将这两个数按照最优二叉树的规则（左孩子<父节点<右孩子）得到父节点的值，将这个值放到上述频率中（相当于合并了两个最小的两个频率）2、按照上述规则进行反复合并与放回。3、得到哈夫曼树。通过上述分析得到每次需要得到两个最小的频率。怎样才能实现每次得到最小的两个频率呢？可以通过数组，但是每次都要排序，很麻烦也很费时间；可以使用第i个顺序统计量的随机算法，但是其复杂度也是很高的。那我们可以选用什么结构呢？这时候就到了之前讲过的优先队列使用优先队列的过程：1、首先需要统计字符串中每个字母的出现频率，由于题目中已经简化问题，将字符限制在小写字符a到小写字符z,2、初始化a到z的出现频率为0，所以在统计完频率频率之后需要借助频率不为0这一重要条件将出现的字符push进入队列。3、每次取出最小的两个相加之后再放入优先队列。退出循环的条件为优先队列为空。下面给出本题代码：

#include <bits/stdc++.h>
#define max_size 10010

using namespace std;

typedef long long LL;
char c[max_size];
long long f[max_size];

priority_queue<LL ,vector<LL>,greater<LL> >q;//建立小顶堆；
long long n,ans;
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        string s;
        cin>>s;
        getchar();
        memset(f,0,sizeof(f));
        int lens=s.size();
        for(int i=1; i<=lens; i++)
        {
            c[i]=s[i-1];
            f[c[i]]++;
        }

        while(!q.empty())
            q.pop();
        for(int i=65; i<=122; i++)
        {
            if(f[char(i)]>0)
            {
                sum++;
                q.push(f[char(i)]);
            }
        }
        ans=0;
        while(q.size()>1)
        {
            LL a=q.top();
            q.pop();
            LL b=q.top();
            q.pop();
            ans+=(a+b); // 因为编码长度和其在树中的层数相关
            q.push(a+b);
        }
        printf("%lldn",ans);
    }
    return 0;
}

可以发现在前面的统计频率不仅仅是为了统计频率，同时也是实现了将其push进优先队列。

下面给出按照哈夫曼树解决问题的代码，可以比较两种方法的优缺点:

1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <iomanip>
  7 #include <cstring>
  8 #include <string>
  9 #define INF 0xFFFFFF
 10 using namespace std;
 11 
 12 typedef struct
 13 {
 14     int parent[1005];
 15     int lchild[1005];
 16     int rchild[1005];
 17     int weight[1005];
 18 } Htree;
 19 
 20 int createHt(Htree &ht)
 21 {
 22     int n = 0;//length;
 23     int min1,min2;
 24     int lchild,rchild;
 25     memset(ht.parent,-1,sizeof(ht.parent));
 26     memset(ht.lchild,-1,sizeof(ht.lchild));
 27     memset(ht.rchild,-1,sizeof(ht.rchild));
 28     memset(ht.weight,0,sizeof(ht.weight));
 29 
 30     string str;
 31     cin>>str;
 32     int uppercase[26], lowercase[26];
 33     memset(uppercase, 0,sizeof(uppercase));
 34     memset(lowercase, 0, sizeof(lowercase));
 35     for(int i = 0; i<str.length(); i++)
 36     {
 37         if(str[i]<91)//uppercase
 38             uppercase[str[i]-65]++;
 39         else
 40             lowercase[str[i]-97]++;
 41     }
 42     for(int i=0; i<26; i++)
 43     {
 44         if(uppercase[i]!=0)
 45         ht.weight[n++] = uppercase[i];
 46     }
 47     for(int i=0; i<26; i++)
 48     {
 49         if(lowercase[i]!=0)
 50         ht.weight[n++] = lowercase[i];
 51     }
 52 
 53     for(int i=n; i<2*n-1; i++)
 54     {
 55         min1=min2=INF;
 56         lchild=rchild=-1;
 57         for(int j=0; j<i; j++)
 58         {
 59             if(ht.parent[j]==-1)
 60             {
 61                 if(ht.weight[j]<min1)
 62                 {
 63                     min2=min1;
 64                     rchild=lchild;
 65                     min1=ht.weight[j];
 66                     lchild=j;
 67                 }
 68                 else if(ht.weight[j]<min2)
 69                 {
 70                     min2=ht.weight[j];
 71                     rchild=j;
 72                 }
 73             }
 74         }
 75         ht.weight[i]=ht.weight[lchild]+ht.weight[rchild];
 76         ht.lchild[i]=lchild;
 77         ht.rchild[i]=rchild;
 78         ht.parent[lchild]=ht.parent[rchild]=i;
 79     }
 80     return n;
 81 }
 82 
 83 int main()
 84 {
 85     int T;
 86     Htree ht;
 87     long long result;
 88     int level;
 89     cin>>T;
 90     while(T--)
 91     {
 92         int len = createHt(ht);
 93         result = 0;
 94         for(int i = 0; i<len; i++)
 95         {
 96             level = 0;
 97             int j = i;
 98             while(ht.parent[j]!=-1)
 99             {
100                 level++;
101                 j=ht.parent[j];
102             }
103             result+=level*ht.weight[i];
104         }
105         printf("%lldn", result);
106     }
107 }

View Code

原文链接: https://www.cnblogs.com/zpfbuaa/p/5002055.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍