哈夫曼树Huffman Tree与合并果子是信息学竞赛里最经典、也最容易拿满分的贪心模型之一。它几乎每年都出现在各大青少年编程赛事中第十八届蓝桥杯全国软件和信息技术大赛软件赛正处于报名季C/C 程序设计、Python 程序设计 科目报名 2026-10-08 10:00—12-18 14:00省赛/全国选拔赛定于 2027 年 4 月中国电子学会 2026 年 12 月青少年软件编程等级考试C/C 一级至十级、Python 一级至六级报名 9/23—12/2、12-12 统考全国青少年信息素养大赛算法应用赛项也把贪心 优先队列列为高频考点。本文用一道原创题带你把哈夫曼贪心吃透。一、题目校园科技节物资搬运——合并果子食堂后山堆放着 n 堆果子第 i 堆质量为 w_i。每次可以挑选任意两堆合并成一堆这次合并消耗的体力等于这两堆质量之和。合并后得到的新堆可以继续参与后续合并直到所有果子合成一堆。求最小的体力总消耗。输入第一行 n第二行 n 个整数 w_1…w_n。输出一个整数表示最小体力消耗。样例输入5 3 4 5 2 1样例输出33提示合并顺序不同总消耗差异巨大。比如[100,1,1,1]如果按输入顺序硬合100110110111021021103总消耗高达 306而先合并轻的1121233100103只要 108。二、核心考点贪心策略的正确性为什么每次都合并当前最轻的两堆一定最优优先队列小根堆如何高效、动态地取出全局最小的两个元素。与哈夫曼树 / 带权路径长度WPL的等价关系总消耗 哈夫曼树的带权路径长度。数据范围与溢出果子数量多、单堆质量大时总消耗会远超int范围必须用long longC或 Python 自带大整数。三、解法拆解思路把每一堆果子看作一个节点初始有 n 个节点每个节点权值 果子质量。每次选权值最小的两个节点 x、y 合并产生一个新节点权值为 xy并把 xy 累加到总消耗里。新节点重新放回候选集合继续选最小的两个……直到只剩一个节点。为什么贪心正确用交换论证一句话理解在任意一棵合并树里质量最小的两个果子一定会在最底层深度最大被合并——如果最优解中它们没在一起把一次合并换成合并这两个最轻的总代价只会更小或不变。所以每次合并最轻两堆不会丢最优性。样例一步步推演w [1, 2, 3, 4, 5]取 1、2 合并 → 新堆 3消耗3候选 {3, 3, 4, 5}取 3、3 合并 → 新堆 6消耗6候选 {4, 5, 6}取 4、5 合并 → 新堆 9消耗9候选 {6, 9}取 6、9 合并 → 新堆 15消耗15只剩一堆总消耗 3 6 9 15 33✅C 解法#include bits/stdc.h using namespace std; using ll long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; if (!(cin n)) return 0; // 小根堆每次取出最小的两个 priority_queuell, vectorll, greaterll pq; for (int i 0; i n; i) { ll x; cin x; pq.push(x); } if (pq.size() 1) { cout 0 \n; return 0; } ll ans 0; while (pq.size() 1) { ll a pq.top(); pq.pop(); ll b pq.top(); pq.pop(); ll s a b; // 本次合并的体力消耗 ans s; // 累加 pq.push(s); // 新堆放回参与后续合并 } cout ans \n; return 0; }Python 解法import heapq def huffman_cost(w): if len(w) 1: return 0 h w[:] heapq.heapify(h) # Python 的 heapq 默认就是小根堆 ans 0 while len(h) 1: a heapq.heappop(h) b heapq.heappop(h) s a b ans s heapq.heappush(h, s) return ans n int(input()) w list(map(int, input().split())) print(huffman_cost(w))四、时间与空间复杂度时间复杂度每个元素进出优先队列各约 O(log n) 次总共O(n log n)。空间复杂度优先队列存放所有堆最坏O(n)。对比朴素做法每次把数组排序取前两个再插回去是 O(n² log n)数据一大就会超时而优先队列把取最小优化到了对数级。五、七大易错点用int存总消耗溢出n 和 w 都大时累计和轻松超过 2³¹C 一定要用long longPython 无此烦恼自动大整数。误用大根堆C 的priority_queue默认是大顶堆必须写成priority_queuell, vectorll, greaterllPython 的heapq默认小顶堆正好契合。n 1 没特判只有一堆果子时消耗为 0直接输出别进循环虽然进循环也安全但显式特判更清晰。忘了把新堆 push 回去合并出的新堆必须重新入堆否则后续合并会漏掉它答案偏小。按输入顺序硬合而非动态取最小a[0]a[1]再a[2]…… 这种顺序合并在[100,1,1,1]上会算出 306而正确哈夫曼是 108。必须每一步都重新取全局最小两堆。多组测试未清空堆 / 重置答案用全局变量时每组数据前要pq priority_queue...()重新构造或ans 0。用sort每轮取前二看似简单实则是 O(n² log n)大数据必 TLE。记住——动态最小两堆用优先队列不是反复排序。六、进阶拓展哈夫曼编码把果子质量换成字符出现频率合并过程就是构造最优前缀编码树带权路径长度 WPL 最小即总编码长度最短。这是压缩算法zip、JPEG的理论基础。每次合并 k 堆若规定每次最多合并 k 堆需先补若干质量为 0 的虚拟堆使(n-1) % (k-1) 0否则最后一次凑不齐 k 堆会导致非最优。WPL 的另一种算法总消耗 Σ每堆质量 × 它在合并树中的深度。叶子越轻应当被压得越深。正确性证明交换论证假设最优合并树中质量最小的两个果子不在同一底层把某次合并替换为合并这两个最小的可证明总代价不增——这就是贪心不会错过最优解的本质。别和 OBST 搞混最优二叉搜索树已知查找概率用的是区间 DP经典石子合并思路与哈夫曼不同哈夫曼只关心合并代价、不关心中序顺序。七、小结与互动哈夫曼合并是贪心 优先队列的标杆题每次合并最轻两堆用一个小根堆 O(n log n) 搞定答案就是哈夫曼树的带权路径长度。牢记 long long 防溢出、小根堆方向、动态取最小三点蓝桥杯与电子学会考级基本稳拿。思考题如果规定每次必须合并恰好 3 堆最少体力该怎么算欢迎在评论区留下你的思路下期我们可以一起拆解k 路合并的虚拟堆补零技巧。如果觉得这篇对你有帮助点个赞 收藏关注我持续更新少儿编程竞赛原创题与双语言题解。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。 
长河君 · 2026/10/26 16:59:21 · 阅读 1.2k 蓝桥杯·全国青少年信息素养大赛·电子学会Python/C++考级：哈夫曼树与合并果子解析
哈夫曼树Huffman Tree与合并果子是信息学竞赛里最经典、也最容易拿满分的贪心模型之一。它几乎每年都出现在各大青少年编程赛事中第十八届蓝桥杯全国软件和信息技术大赛软件赛正处于报名季C/C 程序设计、Python 程序设计 科目报名 2026-10-08 10:00—12-18 14:00省赛/全国选拔赛定于 2027 年 4 月中国电子学会 2026 年 12 月青少年软件编程等级考试C/C 一级至十级、Python 一级至六级报名 9/23—12/2、12-12 统考全国青少年信息素养大赛算法应用赛项也把贪心 优先队列列为高频考点。本文用一道原创题带你把哈夫曼贪心吃透。一、题目校园科技节物资搬运——合并果子食堂后山堆放着 n 堆果子第 i 堆质量为 w_i。每次可以挑选任意两堆合并成一堆这次合并消耗的体力等于这两堆质量之和。合并后得到的新堆可以继续参与后续合并直到所有果子合成一堆。求最小的体力总消耗。输入第一行 n第二行 n 个整数 w_1…w_n。输出一个整数表示最小体力消耗。样例输入5 3 4 5 2 1样例输出33提示合并顺序不同总消耗差异巨大。比如[100,1,1,1]如果按输入顺序硬合100110110111021021103总消耗高达 306而先合并轻的1121233100103只要 108。二、核心考点贪心策略的正确性为什么每次都合并当前最轻的两堆一定最优优先队列小根堆如何高效、动态地取出全局最小的两个元素。与哈夫曼树 / 带权路径长度WPL的等价关系总消耗 哈夫曼树的带权路径长度。数据范围与溢出果子数量多、单堆质量大时总消耗会远超int范围必须用long longC或 Python 自带大整数。三、解法拆解思路把每一堆果子看作一个节点初始有 n 个节点每个节点权值 果子质量。每次选权值最小的两个节点 x、y 合并产生一个新节点权值为 xy并把 xy 累加到总消耗里。新节点重新放回候选集合继续选最小的两个……直到只剩一个节点。为什么贪心正确用交换论证一句话理解在任意一棵合并树里质量最小的两个果子一定会在最底层深度最大被合并——如果最优解中它们没在一起把一次合并换成合并这两个最轻的总代价只会更小或不变。所以每次合并最轻两堆不会丢最优性。样例一步步推演w [1, 2, 3, 4, 5]取 1、2 合并 → 新堆 3消耗3候选 {3, 3, 4, 5}取 3、3 合并 → 新堆 6消耗6候选 {4, 5, 6}取 4、5 合并 → 新堆 9消耗9候选 {6, 9}取 6、9 合并 → 新堆 15消耗15只剩一堆总消耗 3 6 9 15 33✅C 解法#include bits/stdc.h using namespace std; using ll long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; if (!(cin n)) return 0; // 小根堆每次取出最小的两个 priority_queuell, vectorll, greaterll pq; for (int i 0; i n; i) { ll x; cin x; pq.push(x); } if (pq.size() 1) { cout 0 \n; return 0; } ll ans 0; while (pq.size() 1) { ll a pq.top(); pq.pop(); ll b pq.top(); pq.pop(); ll s a b; // 本次合并的体力消耗 ans s; // 累加 pq.push(s); // 新堆放回参与后续合并 } cout ans \n; return 0; }Python 解法import heapq def huffman_cost(w): if len(w) 1: return 0 h w[:] heapq.heapify(h) # Python 的 heapq 默认就是小根堆 ans 0 while len(h) 1: a heapq.heappop(h) b heapq.heappop(h) s a b ans s heapq.heappush(h, s) return ans n int(input()) w list(map(int, input().split())) print(huffman_cost(w))四、时间与空间复杂度时间复杂度每个元素进出优先队列各约 O(log n) 次总共O(n log n)。空间复杂度优先队列存放所有堆最坏O(n)。对比朴素做法每次把数组排序取前两个再插回去是 O(n² log n)数据一大就会超时而优先队列把取最小优化到了对数级。五、七大易错点用int存总消耗溢出n 和 w 都大时累计和轻松超过 2³¹C 一定要用long longPython 无此烦恼自动大整数。误用大根堆C 的priority_queue默认是大顶堆必须写成priority_queuell, vectorll, greaterllPython 的heapq默认小顶堆正好契合。n 1 没特判只有一堆果子时消耗为 0直接输出别进循环虽然进循环也安全但显式特判更清晰。忘了把新堆 push 回去合并出的新堆必须重新入堆否则后续合并会漏掉它答案偏小。按输入顺序硬合而非动态取最小a[0]a[1]再a[2]…… 这种顺序合并在[100,1,1,1]上会算出 306而正确哈夫曼是 108。必须每一步都重新取全局最小两堆。多组测试未清空堆 / 重置答案用全局变量时每组数据前要pq priority_queue...()重新构造或ans 0。用sort每轮取前二看似简单实则是 O(n² log n)大数据必 TLE。记住——动态最小两堆用优先队列不是反复排序。六、进阶拓展哈夫曼编码把果子质量换成字符出现频率合并过程就是构造最优前缀编码树带权路径长度 WPL 最小即总编码长度最短。这是压缩算法zip、JPEG的理论基础。每次合并 k 堆若规定每次最多合并 k 堆需先补若干质量为 0 的虚拟堆使(n-1) % (k-1) 0否则最后一次凑不齐 k 堆会导致非最优。WPL 的另一种算法总消耗 Σ每堆质量 × 它在合并树中的深度。叶子越轻应当被压得越深。正确性证明交换论证假设最优合并树中质量最小的两个果子不在同一底层把某次合并替换为合并这两个最小的可证明总代价不增——这就是贪心不会错过最优解的本质。别和 OBST 搞混最优二叉搜索树已知查找概率用的是区间 DP经典石子合并思路与哈夫曼不同哈夫曼只关心合并代价、不关心中序顺序。七、小结与互动哈夫曼合并是贪心 优先队列的标杆题每次合并最轻两堆用一个小根堆 O(n log n) 搞定答案就是哈夫曼树的带权路径长度。牢记 long long 防溢出、小根堆方向、动态取最小三点蓝桥杯与电子学会考级基本稳拿。思考题如果规定每次必须合并恰好 3 堆最少体力该怎么算欢迎在评论区留下你的思路下期我们可以一起拆解k 路合并的虚拟堆补零技巧。如果觉得这篇对你有帮助点个赞 收藏关注我持续更新少儿编程竞赛原创题与双语言题解。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。