最佳归并树解析

发布时间：2022-07-10 11:56 所属栏目：51 来源：互联网

导读：通过上一节对置换-选择排序算法的学习了解到，通过对初始文件进行置换选择排序能够获得多个长度不等的初始归并段，相比于按照内存容量大小对初始文件进行等分，大大减少了初始归并段的数量，从而提高了外部排序的整体效率。本节带领大家思考一个问题：无论

　　通过上一节对置换-选择排序算法的学习了解到，通过对初始文件进行置换选择排序能够获得多个长度不等的初始归并段，相比于按照内存容量大小对初始文件进行等分，大大减少了初始归并段的数量，从而提高了外部排序的整体效率。

　　本节带领大家思考一个问题：无论是通过等分还是置换-选择排序得到的归并段，如何设置它们的归并顺序，可以使得对外存的访问次数降到最低？

　　假设在进行平衡归并时，操作每个记录都需要单独进行一次对外存的读写，那么图 1 中的归并过程需要对外存进行读或者写的次数为：
　　（9+30+12+18+3+17+2+6+24）*2*2=484（图 1 中涉及到了两次归并，对外存的读和写各进行 2 次）
　　从计算结果上看，对于图 1 中的 3 叉树来讲，其操作外存的次数恰好是树的带权路径长度的 2 倍。所以，对于如何减少访问外存的次数的问题，就等同于考虑如何使 k-路归并所构成的 k 叉树的带权路径长度最短。

　　对于如何判断是否需要增加虚段，以及增加多少虚段的问题，有以下结论直接套用即可：

　　在一般情况下，对于 k–路平衡归并来说，若 (m-1)MOD(k-1)=0，则不需要增加虚段；否则需附加 k-(m-1)MOD(k-1)-1 个虚段。

　　本章用了 4 节的内容介绍了实现外部排序的两个过程：
　　将整个初始文件分为多个初始归并段;
　　将初始归并段进行归并，直至得到一个有序的完整文件；

　　为了提高整个外部排序的效率，本章分别从以上两个方面对外部排序进行了优化：
　　在实现将初始文件分为 m 个初始归并段时，为了尽量减小 m 的值，采用置换-选择排序算法，可实现将整个初始文件分为数量较少的长度不等的初始归并段。
　　同时在将初始归并段归并为有序完整文件的过程中，为了尽量减少读写外存的次数，采用构建最佳归并树的方式，对初始归并段进行归并，而归并的具体实现方法是采用败者树的方式。

（编辑：ASP站长网）