PYTHON LESSON 092
例题精练：合并果子的最少体力
拆解“合并果子”经典题，掌握“每次合并最小两堆”的贪心策略与最小堆实现，会计算总代价。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- heapq.heapify(heap) 一键建堆
- heappop 两次取出最小两堆
- total += a + b 累加每次合并代价
01 · 核心概念
哈夫曼式贪心求最小合并代价
哈夫曼式贪心求最小合并代价：每次把两堆果子并成一堆，花费体力等于两堆重量之和；新堆还要继续参与后面的合并。关键洞察：一堆果子每被合并一次，它的重量就“再被收一次费”——所以越重的堆应该越晚出场，越轻的堆可以多出场。
GESP Python 6 级 · 哈夫曼树GESP Python 6 级 · 哈夫曼编码流程图是算法的表示方法，不是 Python 语法。
02 · 语法与规则
先记住这 3 条，再开始写程序
heapq.heapify(heap) 一键建堆先准确读出这条写法的结构与作用。
heappop 两次取出最小两堆换一组最小数据，手工推演一次结果。
total += a + b 累加每次合并代价再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 例题精练：合并果子——每次合并的体力消耗等于两堆重量之和
import heapq
fruits = [1, 2, 3, 4, 5] # 5 堆果子的重量
heap = fruits[:]
heapq.heapify(heap) # 一键把列表变成最小堆
total = 0
step = 0
print("初始果堆：", heap)
while len(heap) > 1:
a = heapq.heappop(heap) # 最轻的一堆
b = heapq.heappop(heap) # 第二轻的一堆
cost = a + b
total = total + cost
step = step + 1
print("第", step, "次合并：", a, "+", b, "=", cost, "，累计体力", total)
heapq.heappush(heap, cost)
print("全部合成 1 堆，最少耗费体力：", total)初始果堆： [1, 2, 3, 4, 5] 第 1 次合并： 1 + 2 = 3 ，累计体力 3 第 2 次合并： 3 + 3 = 6 ，累计体力 9 第 3 次合并： 4 + 5 = 9 ，累计体力 18 第 4 次合并： 6 + 9 = 15 ，累计体力 33 全部合成 1 堆，最少耗费体力： 33
4 次合并代价之和 3+6+9+15=33，正好等于哈夫曼树的带权路径长度 WPL。
04 · 逐步理解
每一步只解决一个问题
- 01
读题：代价到底怎么算
每次把两堆果子并成一堆，花费体力等于两堆重量之和；新堆还要继续参与后面的合并。关键洞察：一堆果子每被合并一次，它的重量就“再被收一次费”——所以越重的堆应该越晚出场，越轻的堆可以多出场。
- 02
思路：最小的两堆先合并
最轻的两堆先合并，它们被收费次数最多但单价最低；重堆留到最后，只被收一两次费。每一步都拿当前最小的两堆，这就是贪心选择，也正是第 4 课哈夫曼树的造树过程换了个故事外壳。
a = heapq.heappop(heap) b = heapq.heappop(heap) - 03
编码：最小堆自动维持秩序
列表 heapify 之后，heappop 永远弹出最小值；合并出的新堆 heappush 回去自动归位，不用手动排序。循环到只剩一堆为止，循环次数恰好是“堆数 - 1”。
while len(heap) > 1: a = heapq.heappop(heap) b = heapq.heappop(heap) heapq.heappush(heap, a + b) - 04
验证：小样例手算对拍
拿三堆 [1, 2, 3] 手算：先合 1+2=3，再合 3+3=6，总代价 9。故意换个顺序：2+3=5、1+5=6，总代价 11——确实更贵。小样例对拍通过，再放心交给大数据。
- 05
与哈夫曼编码的关系
把“果堆重量”换成“字符频次”，把“体力”换成“编码长度 × 次数”，这道题就变回了文件压缩课的哈夫曼编码。同一个模型换层皮就是另一道题，考级最爱这样出——看穿模型，题目就熟了。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，跟踪 4 次合并中每堆果子的去向
- 2把果堆改成 [3, 1, 4, 1, 5, 9] 再跑一次
- 3手算 [1, 2, 3] 的最小总代价并核对
- 4想一想：为什么先合并大堆一定更累
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
完成检查