最佳归并树

哈夫曼树

始终归并两个最小的叶子节点，将归并后的节点看作新的叶子节点

归并书的带权路径长度

WPL 路径长度和节点的值 磁盘I/O次数

构造哈夫曼树实现最佳归并树

多路归并时虚设长度为0的段

添加虚段的数量

k路归并的最佳归并树一定是一颗严格的k叉树
树中只包含度为0的节点和度为k的节点
设度为k的节点有nk个
度为0的节点有n0个
节点总数为n个
则 初始归并段数量 + 虚段数量 = n0
n = n0 + nk
k nk = n - 1(减去的是根节点，因为根节点入度为0，其余节点入读均为1)
nk = (n0 - 1)/(k - 1)

结论

1. (初始归并段 - 1)%(k - 1) = 0 : 刚好构成严格k叉树，不需要添加虚段
2. (初始归并段 - 1)%(k - 1) = u : 不构成严格的k叉树，需要添加k - 1 - u个虚段

例子

8路归并 初始归并段 = 19
n0 - 1 = 19 - 1 = 18
u = (n0 - 1) % (k - 1) = 18 % (8 - 1) = 4
需要补充k - 1 - u = 8 - 1 - 4 = 3个虚段

总结

理论基础

1. 每个初始归并段对应一个叶子节点，把归并段的块数作为叶子节点的权值
2. 归并树的WPL = 树中所有叶子节点的带权路径之和
3. 归并过程中磁盘的I/O次数 = 归并树的WPL * 2

注意

k叉归并树的最佳归并树一定是严格k叉树，即树中只有度为k的节点和度为0的节点（非叶子节点度为k）

如何构造

1. 补充虚段
   • 若 (初始归并段数目 - 1)%(k - 1) = 0，则不需要添加虚段
   • 若(初始归并段数目 - 1)%(k - 1) = u != 0, 则需要添加 k - 1 - u 个虚段
2. 构造k叉哈夫曼树：每次选取k个根节点全职最小的树合并，并将k个根节点的权值之和作为新的根节点的权值