蓝桥杯·全国青少年信息素养大赛·电子学会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

样例输出：

提示：合并顺序不同，总消耗差异巨大。比如[100,1,1,1]如果按输入顺序硬合（100+1=101，101+1=102，102+1=103）总消耗高达 306；而先合并轻的（1+1=2，1+2=3，3+100=103）只要 108。

二、核心考点

贪心策略的正确性：为什么"每次都合并当前最轻的两堆"一定最优？
优先队列（小根堆）：如何高效、动态地取出全局最小的两个元素。
与哈夫曼树 / 带权路径长度（WPL）的等价关系：总消耗 = 哈夫曼树的带权路径长度。
数据范围与溢出：果子数量多、单堆质量大时，总消耗会远超int范围，必须用long long（C++）或 Python 自带大整数。

三、解法拆解

思路

把每一堆果子看作一个节点，初始有 n 个节点，每个节点权值 = 果子质量。每次选权值最小的两个节点 x、y 合并，产生一个新节点，权值为 x+y，并把 x+y 累加到总消耗里。新节点重新放回候选集合，继续选最小的两个……直到只剩一个节点。

为什么贪心正确？用交换论证一句话理解：在任意一棵合并树里，质量最小的两个果子一定会在最底层（深度最大）被合并——如果最优解中它们没在一起，把一次合并换成合并这两个最轻的，总代价只会更小或不变。所以"每次合并最轻两堆"不会丢最优性。

样例一步步推演（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_queue<ll, vector<ll>, greater<ll>> 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 long；Python 无此烦恼（自动大整数）。
误用大根堆：C++ 的priority_queue默认是大顶堆，必须写成priority_queue<ll, vector<ll>, greater<ll>>；Python 的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（经典"石子合并"思路），与哈夫曼不同；哈夫曼只关心合并代价、不关心中序顺序。