11.5 最佳归并树

01最佳归并树

1、假设由置换-选择得到9个初始归并段，其长度（即记录数）依次为：9,30,12,18,3,17,2,6,24。现作3-路平衡归并，其归并树（表示归并过程的图）如下图所示，

图中每个圆圈表示一个初始归并段，圆圈中数字表示归并段的长度。假设每个记录占一个物理块，则两趟归并所需对外存进行的读/写次数为：（9+30+12+18+3+17+2+6+24）*2*2=484。若将初始归并段的长度看成是归并树中叶子结点的权，则此三叉树的带权路径长度的两倍恰好为484。显然，归并方案不同，所得归并树亦不同，树的带权路径长度也不同。

2、若对长度不等的m个初始归并段，构造一棵赫夫曼树作为归并树，便可使在进行外部归并时所需对外存进行的读/写次数达最少。

C语言打印出心形表白，初学C语言也能看懂！！​ mp.weixin.qq.com

文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。

原文链接：zhuanlan.zhihu.com/p/338816023