设给定权集 W={5,7,2,3,6,8,9}，构造关于 W 的一棵哈夫曼树，并求其带权路径长度 WPL。

[tag_link]

参考答案

依次合并两个最小权值：2+3=5，5+5=10，6+7=13，8+9=17，10+13=23，17+23=40。因此 WPL=5+10+13+17+23+40=108。

推导过程

叶深复核：2、3 的深度为 4，原权值 5、6、7 的深度为 3，8、9 的深度为 2；故 WPL=(2+3)×4+(5+6+7)×3+(8+9)×2=108。左右子树可以互换，不影响 WPL。

复杂度与边界

最小堆构造时间 O(n log n)、空间 O(n)；单权值时 WPL=0。

易错点

每次都要把新权值放回集合；WPL 是各次合并权值之和，不是叶权值之和。

评分要点

• 写全六次合并
• 得出 WPL=108
• 能用叶深或合并和复核