Huffman树、编码与最优前缀码

考点定位

本课深化 Huffman树、编码与最优前缀码。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

Huffman算法每次合并权值最小的两棵树，合并权值重新入队。叶结点编码天然满足前缀码；带权路径长度等于全部合并权值之和。

算法推演

用最小堆反复取出x,y，累加x+y并压回；直到堆中只剩根。权值相同时树形可不同，但最小WPL相同。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

每轮堆中元素表示尚未合并的子树，其权值为该子树全部叶权之和。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：Huffman编码最优针对给定权值和二进制前缀码目标，不保证编码树唯一。

随课应用

权值为2、3、7、9的Huffman树，其最小带权路径长度WPL是多少？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。