5.5 选择题讲评：WPL 与并查集复杂度

哈夫曼题每轮必须从当前所有候选权值中取两个最小，最稳方法是写有序多重集合。WPL 等于所有合并权值之和。并查集题则先找根再合并，代表元本身没有固定业务含义。

手工推演

权值 1、1、3、5：合并2，候选2、3、5；合并5，候选5、5；合并10，WPL=2+5+10=17。

结构与代码

多选：A 哈夫曼树无一度结点；B 最优树形一定唯一；C 路径压缩优化 find；D 按大小合并应比较两个根的集合规模。答案 A、C、D。

错解反馈

合并同权值时因形状不同误判 WPL 不同；把哈夫曼编码当等长码；并查集一次 find 后声称所有结点都已压到根。

迁移练习

6 个叶的哈夫曼树总结点数是多少？答案11。验收要求由 $n_0=n_2+1$ 推导。