来源：百度文库 编辑：九乡新闻网 时间：2024/04/28 17:30:09
如何从N个数(一堆已排序文件中)中选出最大（小）的n个数？也许有些人对loser tree不是很了解，其实它是一个比较经典的外部排序方法，也就是有x个已经排序好的文件，将其归并为一个有序序列。败者树的思想咋一看有些绕，其实是为了减小比较次数。首先简单介绍一下败者树：败者树的 叶子节点是数据节点，然后两两分组（如果节点总数不是2的幂，可以用类似完全树的结构构成树），内部节点用来记录左右子树的优胜者中的“败者”（注意记录 的是输的那一方），而优胜者则往上传递继续比较，一直到根节点。如果我们的优胜者是两个数中较小的数，则根节点记录的是最后一次比较中的“败者”，也就是 所有叶子节点中第二小的那个数，而最小的那个数记录在一个独立的变量中。这里要注意，内部节点不但要记录败者的数值，还要记录对应的叶子节点。如果是用链 表构成的树，则内部节点需要有指针指向叶子节点。这里可以有一个trick，就是内部节点只记录“败者”对应的叶子节点，具体的数值可以在需要的时候间接 访问（这一方法在用数组来实现败者树时十分有用，后面我会讲到）。关键的来了，当把最小值输出后，最小值所对应的叶子节点需要变成一个新的数（或者改为无穷大，在文件归并的时候表示文件已读完）。接下来维护败者树， 从更新的叶子节点网上，依次与内部节点比较，将“败者”更新，胜者往上继续比较。由于更新节点占用的是之前的最小值的叶子节点，它往上一直到根节点的路径 与之前的最小值的路径是完全相同的。内部节点记录的“败者”虽然称为“败者”，但却是其左子树或者右子树中最小的数。也就是说，只要与“败者”比较得到的胜者，就 是该子树中最小的那个数（这里讲得有点绕了，看不明白的还是找本书看吧，对照着图比较容易理解）。注：也可以直接对N构建败者树，但是败者树用数组实现时不能像堆一样进行增量维护，当叶子节点的个数变动时需要完全重新构建整棵树。为了方便比较堆和败者树的性能，后面的分析都是对n个数构建的堆和败者树来分析的。 总而言之，败者树在进行维护的时候，比较次数是logn+1。与堆不同的是，败者树是从下往上维护，每上一层，只需要和败者节点比较“一次”即可。而堆在维护的时候是从上往下，每下一层，需要和左右子节点都比较，需要比较两次。从这个角度，败者树比堆更优一些。但是，请注意但是，败者树每一次维护必定需要从叶子节点一直走到根节点，不可能中间停止；而堆维护时，“有可能”会在中间的某个层停止，不需要继续往下。这样一来，虽然每一层败者树需要的比较次数比堆少一倍，但是走的层数堆会比败者树少。具体少多少，从平均意义上到底哪一个的效率会更好一些？那我就不知道了，这个分析起来有点麻烦。感兴趣的人可以尝试一下，讨论讨论。但是至少说明了，也许堆并非是最优的。 具体到我们的问题。类似的方法，先构建一棵有n个叶子节点的败者树，胜出者w是n个中最小的那一个。从N中读入一个新的数m后，和w比较，如果比w小，直接丢弃，否则用m替换w所在的叶子节点的值，然后维护该败者树。依次执行，直到遍历完N，败者树中保留的n个数就是N中最大的n个数。时间复杂度也是O（Nlogn） 前面有提到，堆的优点中包括“完全树”，“用数组实现”，以及“父节点与左右子节点之间的下标的特殊关系”。其实败者树也可以用数组来实现。其实我以前没有这么想过，我进微软实习的时候的考我的编程题就是文件归并，我是用败者树做的，当时是用指针来构建树，2个小时的题，我弄了3个小时才弄出来，差点没弄死我。指针维护起来太麻烦了。昨天旁边的David提到败者树可以用数组实现，恍然大悟。其原理和堆的数组实现是相同的，唯一的区别是堆的所有节点都是数据节点，而败者树只有叶子节点是数据节点。所以在空间复杂度上，败者树所需的空间大小是堆的一倍（完全树的内部节点的个数是叶子节点个数减一）。
九乡新闻网