外部排序中堆和失败树有什么区别？
我觉得它们彼此非常相似，除了一些概念。在外部排序中，它们的功能基本相同，即在k次运行中找到最小值/最大值。那么他们两者之间有一些显着的差异吗？
I felt that they are very similar to each other, except at some concepts. In external sorting their functions are basically the same, that is to find the minimal/maximal value in k runs. So are there some significant differences between them two ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在大多数情况下，失败者树和堆非常相似。然而，有一些重要的区别。失败者树因为它提供了每场比赛的失败者，所以将包含重复节点。由于堆是一种数据存储结构，因此它不会包含这些冗余。两者之间的另一个区别是，失败者树必须是完整二叉树（因为它是锦标赛树的一种），但堆不一定必须是二叉树。
最后，要了解失败者树的具体质量，请考虑以下问题：
假设我们有 k 个序列，每个序列都按非降序排序，并且要按非降序合并为一个序列。这可以通过将具有最小键的元素重复传输到输出数组来实现。必须从 k 序列中的前导元素中找到最小的键。通常，这需要对每个传输的元素进行 k − 1 次比较。然而，使用失败者树，可以将每个元素减少到 log2 k 次比较。
资料来源：《数据结构与应用手册》，Dinesh Mehta
For the most part, loser trees and heaps are quite similar. However, there are a few important distinctions. The loser tree, because it provides the loser of each match, will contain repeat nodes. Since the heap is a data-storing structure, it won't contain these redundancies. Another difference between the two is that the loser tree must be a full binary tree (because it is a type of tournament tree), but the heap does not necessarily have to be binary.
Finally, to understand a specific quality of the loser tree, consider the following problem:
Suppose we have k sequences, each of which is sorted in nondecreasing order, that are to be merged into one sequence in nondecreasing order. This can be achieved by repeatedly transferring the element with the smallest key to an output array. The smallest key has to be found from the leading elements in the k sequences. Ordinarily, this would require k − 1 comparisons for each element transferred. However, with a loser tree, this can be reduced to log2 k comparisons per element.
Source: Handbook of Data Structures and Applications, Dinesh Mehta