(73)王道数据结构-最佳归并树

基本概念

1.每个初始化归并段对应一个叶子结点，把归并段的块数作为叶子的权值

2.归并树的WPL=树中所有叶子节点的带权路径长度之和

3.归并过程中的磁盘I/O次数=归并树的WPL*2

k叉归并的最佳归并树一定是严格k叉树，即树中只有度为k、度为0的结点

构造方法

1.补充虚段

• 若（初始归并段数量-1）%（k-1）=0，说明刚好可以构造严格k叉树，此时不需要添加虚段
• 若（初始归并段数量-1）%（k-1）=u≠0，则需要补充（k-1）-u个虚段

2.构造k叉哈夫曼树

• 每次选择k给根节点权值最小的树合并，并将k个根节点的权值之和作为新的根节点的权值