P1562 哈夫曼编码 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2026年3月11日 19:25

哈夫曼编码题解：still priority_queue->minH

P1562

回复 0 | 赞 0 | 浏览 5

#include <bits/stdc++.h> using namespace std; int main() { string s; while(cin>>s) { if(s=="END") break; int count[130]={0}; for(int i=0;i<s.size();i++) count[s[i]]++; priority_queue<int,vector<int>,greater<int>> minHeap; for(in...

2026年3月5日 18:53

哈夫曼编码题解：

P1562

回复 0 | 赞 2 | 浏览 67

#include <bits/stdc++.h> using namespace std; int anum[27]; int getval() { priority_queue<int,vector<int>,greater<int> >q; for (int i=0;i<27;i++) { if (anum[i]!=0) { q.push(anum[i]); } } int ans =0; if (q....

2026年2月13日 11:07

哈夫曼编码题解：非叶节点累加和 = WPL

P1562

回复 0 | 赞 10 | 浏览 154

注意点：思路：定义 priority_queue ，修改为小顶堆，遍历字符，map记录不同字的出现次数（权重），权重输入到 queue中，其中非叶节点的和，就是哈夫曼编码的长度。推导： AAAAABCD = 5 1 1 1 = 1 1 1 5， (1 + 1) * 3 + 1 * 2 + 5 = 13 = 2 + 3 + 8 。即非叶节点累加和 = WPL = 叶节点 * 对应路径长度的累加和。注意当只有一种字符时，例如 AAAAAAA，则硬编码为 0 或者 1 都可以，即只占用了 1个bit，相比 ASCI...

2025年3月14日 17:35

哈夫曼编码题解：

P1562

回复 0 | 赞 2 | 浏览 1.1k

/*注意只有一个字符的情况比如：AAAAA*/ #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct afman { int a; double b; double c; }afman; //快速排序 int povisition(int a[], int low, int high) { &nb...

2025年3月2日 13:38

哈夫曼编码题解：

P1562

回复 0 | 赞 11 | 浏览 1.4k

#include<bits/stdc++.h> using namespace std; int main(){ char s[100]; while(cin>>s){ int a1,w; double a3; map<char,int>...

2024年4月8日 16:17

哈夫曼编码题解：通过率50%，哪种情况没考虑到呢？

P1562

回复 2 | 赞 7 | 浏览 1.7k

//输出字符串最佳无前缀可变长度编码的位长度 #include<bits/stdc++.h> using namespace std; int main() { string s; while(cin >> s) { if(s == "END") break; int len ...

Cookie‘s AE86

2024年3月25日 15:43

哈夫曼编码题解：c++优先队列实现，注意全为同一字符的特殊情况，例如

P1562

回复 0 | 赞 23 | 浏览 2.0k

#include<bits/stdc++.h> using namespace std; void func(string s){ int len = s.size(); set<char> myset; for(int i = 0; i < len ;i++) myset.insert(s[i]); //获得每种字符使用频率的优先队列 priority_queue<int, vector<int>, greater<int>> pq; ...

2022年8月8日 11:16

哈夫曼编码的坑

P1562

回复 1 | 赞 25 | 浏览 7.0k

思路：通过遍历字符串，统计各个字符的数量，利用map记录遍历map，将map的值（字符数量）加入优先队列常规操作，两个小的数字出队，加上的和进入队列，直到队列长度为1 坑就在于，队列的起始长度可能为1，所以需要单独处理代码 #include <bits/stdc++.h> using namespace std; int main() { priority_queue<int,vector<int>,greater<int>> q; //升序排列 ...

快乐小土狗

2022年9月26日 12:41

题解：哈弗曼编码

P1562

回复 0 | 赞 17 | 浏览 7.0k

#include<bits/stdc++.h> using namespace std; string str; int len, num[30]; int bfs() { priority_queue<int, vector<int>, greater<int> > q; // 创建优先队列，从小到大排序 for(int i = 0; i < 30; i++) { if(num[i]) q.push(num[i]); // 放入每个字母的个数 } int sum = ...

2022年7月8日 21:54

哈夫曼编码应用

P1562

回复 0 | 赞 2 | 浏览 5.7k

此题本质就是将各个字母出现次数作为叶节点权值，然后求带权路径长度，最后还是通过创建小根堆计算非叶节点大小z

1
2

题目哈夫曼编码

题解数量13

发布题解在线答疑

热门题解

1 哈夫曼编码的坑

2 哈夫曼编码题解：c++优先队列实现，注意全为同一字符的特殊情况，例如：BBBBBBBBBB

3 题解：哈弗曼编码

4 哈夫曼编码题解：

5 哈夫曼编码题解：非叶节点累加和 = WPL

6 哈夫曼编码题解：通过率50%，哪种情况没考虑到呢？

7 优先队列c++

8 WPL结论

9 哈夫曼编码应用

10 哈夫曼编码题解：