《第14周外排序第4讲-磁盘排序-最佳归并树.pdf》由会员分享，可在线阅读，更多相关《第14周外排序第4讲-磁盘排序-最佳归并树.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、11.2.3 最佳归并树最佳归并树 k路路平衡归并适合平衡归并适合初始归并段中的记录个数相同的情况初始归并段中的记录个数相同的情况，当当 初始归并段中的初始归并段中的记录个数不同记录个数不同时时，怎么办怎么办 ？ 当当初始归并段和初始归并段和k已确定的已确定的情况时情况时 哪些初始归并段先归并哪些初始归并段先归并，哪些后哪些后归并的问题归并的问题。 归并方案转化为归并方案转化为 显然采用显然采用k叉叉哈夫曼哈夫曼树的归并方案树的归并方案。 剩下只有剩下只有2个归并段个归并段 了了，怎么办怎么办？ 存在的问题（假设存在的问题（假设k=3）：）： WPL最小最小 在内存中归并时，可以利用败者树减少
2、关键字比较次数在内存中归并时，可以利用败者树减少关键字比较次数 解决的方法是加虚段解决的方法是加虚段（长度为长度为0的归并的归并段段） 应加应加(k- -1)- -(m- -1) Mod (k- -1)个个长度的长度的虚段虚段 前面问题的解决方法前面问题的解决方法：加上加上1个虚段个虚段： 加多少个虚段呢加多少个虚段呢？ 若若x=(m- -1) Mod (k- -1)0，则需附加则需附加(k- -1)- -x个虚个虚段段，以使每以使每 次归并都可以对应次归并都可以对应k个段个段。 按照按照哈夫曼树的构造原则哈夫曼树的构造原则（权值越权值越小小的节点离根节点越的节点离根节点越远远） 构造最佳归并
3、树构造最佳归并树。 最佳归并树最佳归并树（m个初始归并段个初始归并段）是带权路径长度最短的是带权路径长度最短的k叉叉 （阶阶）哈夫曼树哈夫曼树，构造步骤如下构造步骤如下： k=2时，时， x=(m- -1) Mod 1 = 0，所以二路归并（哈夫曼树构造中），所以二路归并（哈夫曼树构造中） 不需要增加虚段不需要增加虚段 【例例11- -3】 设文件经设文件经预处理预处理后，得到后，得到长度长度为为 47，9，39，18，4，12，23，7，21，16，26 的的11个初始归并段，试为个初始归并段，试为4路归并设计一个读写文件次数最少的路归并设计一个读写文件次数最少的 归并归并方案（假如每个记录
4、占用一个物理块）。方案（假如每个记录占用一个物理块）。 各个初始归并段中的记录个数，而非关键字序列 解解：初始初始归并归并段个数段个数m=11，k=4。x=(m- -1) Mod (k- -1)=10，因因 此需附加此需附加： (k- -1)- -x = 2 个长度为个长度为0的虚段的虚段。根据集合根据集合： 49，9，35，18，4，12，23， 7，21，14，26，0，0 构造构造4阶哈夫曼树阶哈夫曼树。 4路最佳路最佳归并归并树的构造过程树的构造过程： 0047 1118212326 88 91214 46 3549 218 WPL = (4+7)3+(9+12+14+18+21+23
5、+26)2+(35+49)1 = 363 最少的读写次数最少的读写次数 = 2WPL = 726次次。 按记录个数递增按记录个数递增排序排序：0，0，4，7，9，12，14，18，21，23，26，35，49 【例例11- -4】有有4个初始归并段，记录个数分别为个初始归并段，记录个数分别为2、3、5、8， 采用采用3路归并，最少的读写次数是多少（假设每个记录读写一次）？路归并，最少的读写次数是多少（假设每个记录读写一次）？ 023 5 58 18 WPL = (2+3) 2+(5+8) 1 = 23 最少的读写次数最少的读写次数 = 2 读次数读次数 = 46 解：解：3路最佳归并树如下：路
6、最佳归并树如下： 满足满足k路路平衡归并的前提平衡归并的前提平衡归并树平衡归并树 最佳归并树最佳归并树 例如例如：初始归并段个数初始归并段个数m=8，每个段的记录数每个段的记录数=10，k=2,对应的平衡归并树对应的平衡归并树： 10个记录个记录10个记录个记录 20个记录个记录 10个记录个记录10个记录个记录 20个记录个记录 40个记录个记录 10个记录个记录10个记录个记录 20个记录个记录 10个记录个记录10个记录个记录 20个记录个记录 40个记录个记录 80个记录个记录 与与2路最佳归并树相同路最佳归并树相同。 WPL=8103=240 归并方案设计归并方案设计： 满足满足k路
7、路平衡归并的前提平衡归并的前提 采用采用平衡归并树平衡归并树； 否则否则 采用最佳归并树采用最佳归并树 【例例11- -5】设有设有6个个有序文件有序文件A、B、C、D、E、F，分别含有，分别含有10、 35、40、50、60和和200个数据元素，个数据元素，各文件中各文件中元素按升序排序元素按升序排序。 要求要求通过通过5次两两合并，将次两两合并，将6个文件最终个文件最终合并成一个合并成一个升序文件。升序文件。 给出文件读写次数最少的给出文件读写次数最少的合并合并过程（假设每个记录读写一次）过程（假设每个记录读写一次） 。 两两合并两两合并二路归并二路归并 2路最佳归并树路最佳归并树最少的合并过程最少的合并过程 解解：构造构造2路最佳归并树路最佳归并树，归并过程如下归并过程如下： 195 1035 45 AB 40 85 C 5060 110 DE 200 395 F WPL = (10+35)4+(40+50+60)3+2001 = 830。 最少读写次数最少读写次数 = 2WPL = 1660