5.5.1 哈夫曼树与编码

给定叶权值，带权路径长度 WPL 是各叶权值乘根到叶边数之和。哈夫曼算法反复取两个最小权值合并，生成最小 WPL 的二叉树。权值相同可能得到不同形状，但最小 WPL 相同。

手工推演

权值 2、3、7、9：合并 2+3=5，再 5+7=12，再 9+12=21。WPL 可由每次合并和相加得 $5+12+21=38$。编码时左0右1，可得前缀码；具体码字随左右摆放变化，但长度与 WPL 对应。

结构与代码

优先队列实现每次取两个最小值，复杂度 $O(n\log n)$。只有叶结点承载给定权值，生成树无一度结点，因此 $n$ 个叶共有 $2n-1$ 个结点。

错解反馈

按初始权值排序后一次相邻配对，不把新权重新参与最小选择；把所有结点权都计入 WPL；认为最优编码唯一。

迁移练习

权值 1、2、4、8 求 WPL。合并3、再7、再15，总和25。独立验收：画树并用叶深加权再次核对。