给定权值(7,18,3,32,5,26,12,8),求其加权路径长度WPL

Question

给定权值(7,18,3,32,5,26,12,8),求其加权路径长度WPL

Answer 1

这里WPL是哈夫曼树的带权路径长度.
首先根据给点权值 排序一下 3 5 7 8 12 18 26 32
首先选择两个最小的权值组成一个新树,树的权值为左右子树权值的和,新的权值放回到序列中,变为：
7 8 8 12 18 26 32
/ \
3 5
再选择两个权值最小的点组成新树（这里选择 7 8）,新的取值为7+8 = 15
8 12 15 18 26 32
/ \ / \
3 5 7 8
按照这样的方法直到只剩下一颗树为止,最终哈夫曼树为：
111
/ \
46 65
/ \ / \
20 26 32 33
/ \ / \
8 12 15 18
/ \ / \
3 5 7 8
WPL值为所有点的路径长度*权值之和
WPL = 3*4+ 5*4 + 7*4+8*4 + 12*3 + 18*3 + 26*2 + 32 *2 = 298