7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

m-路归并排序可用一棵m叉树描述,因为每一次作m路归并都需要m个归并段参加,因为,归并段树是一棵只有度为0和度为m的结点的严格m叉树。

设由置换-选择排序得到9个初始归并段,其长度(记录数)依次为:9,30,12,18,3,17,2,6,24。

现作3-路归并,各叶结点表示参加归并的一个初始归并段,叶结点上的权值表示初始归并过程中的记录数,根结点表示最终生成的归并段,叶结点到根结点的路径长度表示归并过程中的归并趟数,各非叶结点代表归并成的新的归并段,则归并树的带权路径长度WPL即为归并过程中的总记录数,因而在归并过程中,总的I/O次数为2*WPL=484。

归并方案不同,所得归并树亦不同,树的带权路径长度(外存I/O次数亦不同)。为了优化归并树的WPL,可以将Huffman树的思想推广到M叉树的情形。在归并树中,让记录数少的初始归并段最先归并,记录数多的初始归并段最晚归并,就可以建立总的I/O次数达到最少的最佳归并树。对上述9个初始归并段可构造成最佳归并树,按此树进行归并,仅需对外村进行446次读写,这棵树便称为最佳归并树。

Huffman树是一棵严格3叉树。若只有8个初始归并段,设上例中少了一个长度为30的归并段。如果在设计归并方案时,缺额的归并段留着最后,即除了最后一次作2-路归并外,其他各次归并仍都是3-路归并,此归并方案的外存读写次数为386。显然不是最佳方案。

正确的做法是,若初始归并段不足构成一棵严格m叉树时,需添加长度为0的“虚段”,按照Huffman树的原则,权为0的叶子应离根最远。

如何判定添加虚段的数目?

设度为0的结点有N0(=n)个,度为m的结点有Nm个,则对严格m叉树有N0=(m-1)Nm+1,由此可以得出Nm=(N0-1)/(m-1)。

如果(N0-1)%(m-1)=0(%为取余运算),则说明这N0个叶结点(初始归并段)正好可以构造m叉归并树。此时,内结点有Nm个。

如果(N0-1)%(m-1)=u不等于0,则说明对于这N0个叶结点,其中有u个多余,不能包含在m叉归并树中。为构造包含所有N0个初始归并段的m叉归并树,应在原有Nm个内结点的基础上再增加一个内结点。它在归并树中代替了一个叶结点位置,被代替的叶结点家伙是哪个刚才多出的u个叶结点,再加上m-u-1个空归并段,就可以建立归并树。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏自学笔记

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

10430
来自专栏电光石火

HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

240100
来自专栏desperate633

LintCode 子集题目代码

8530
来自专栏cmazxiaoma的架构师之路

通过分析LinkedHashMap了解LRU

我们都知道LRU是最近最少使用,根据数据的历史访问记录来进行淘汰数据的。其核心思想是如果数据最近被访问过,那么将来访问的几率也更高。在这里提一下,Redis缓存...

16530
来自专栏desperate633

HashSet实现原理分析(Java源码剖析)add(E e)remove(Object o)iterator()小结

本文将深入讨论HashSet实现原理的源码细节。在分析源码之前,首先我们需要对HashSet有一个基本的理解。

28430
来自专栏用户画像

6.2.2 折半查找

折半查找,又称二分查找,它适用于有序的顺序表。基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则...

7310
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

40270
来自专栏架构之路

Combination Sum II 组合数求和之2-Leetcode

原题: Given a collection of candidate numbers (C) and a target number (T), find al...

31250
来自专栏Java帮帮-微信公众号-技术文章全总结

HashSet 源码分析【面试+工作】

在工作中,经常有这样的需求,需要判断某个ID是否在某个组的管理之下等,就需要查询该组下的ID放到一个集合中,且集合中元素不能有重复,之后判断该集合是否包含我们的...

12630
来自专栏LeetCode

LeetCode <二分搜索>34.Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and...

25250

扫码关注云+社区

领取腾讯云代金券