018-Huffman树-贪心-《算法设计技巧与分析》M.H.A学习笔记
发布时间：2020-12-13 21:12:14 所属栏目：PHP教程 来源：网络整理
导读：Huffman 树 是完全2叉树，权重较大的节点距离根较近。 Huffman 编码 是 1种编码方法，该方法完全根据 字符 出现几率来构造异字头的平均长度最短的码字 。 基本思路： 建立 Huffman 树的进程： 假定有 n 个权，则构造出的哈夫曼树有 n 个叶子结点。 n 个权分
|
Huffman树是完全2叉树，权重较大的节点距离根较近。 Huffman编码是1种编码方法，该方法完全根据字符出现几率来构造异字头的平均长度最短的码字。
基本思路：建立Huffman树的进程： 假定有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为： (1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树唯一1个结点)； (2) 在森林当选出两个根结点的权值最小的树合并，作为1棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩1棵树为止，该树即为所求得的哈夫曼树。
选取权值最小的结点时我们用最小堆。 需要得出各个字母的具体编码，我们只需要在所有的左儿子的边标上0，右儿子的边标上1，从根节点到目标节点的所有经过的边的码就是该字母的编码。 算法分析： 假定有n个字符。 把所有字符插入堆需要Θ(n)，从堆中删除两个元素和新加1个元素需要O(log n)。重复n⑴次，所以总的时间复杂度是O(n log n)。 伪代码：
C++代码：//计算哈夫曼编码下的文本占的位数，并与定长编码的比较。
#include<iostream>
#include<string>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<queue> //哈夫曼树，用优先队列实现
using namespace std;
int main()
{
string s;
while (cin >> s)
{
if (s == "END") break;
int len = s.size();
int date[30] = { 0 }; //date数组记录text中各个字符的频数
priority_queue<int>q;
for (int i = 0; i < len; i++)
{
if (s[i] == '_') date[0]++;
else date[s[i] - 'A' + 1]++;
}
for (int i = 0; i < 27; i++)
{
if (date[i]!=0) q.push(-date[i]); //只把不同字符的频数加入优先队列，字符本身与题目要求无关
} //处理使小的数据的优先级别高
int ans = 0;
int tem;
while (!q.empty())
{
tem = -q.top(); //取出最小的两个数，相加累计到ans中，并加入队列，1直处理到队列中没有数
q.pop();
if (!q.empty())
{
tem = tem - q.top();
q.pop();
}
ans = ans + tem;
if (!q.empty())
q.push(-tem); //若队列已没有数据，则不添加（上面已取出最后两个，或1个），若没有这1步，上面whlie的判断不成立。
}
int ans8 = len << 3;
double bi = (double)ans8 / ans;
printf("%d %d %.1lfn",ans8,ans,bi);
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
