Fly*_*ind 8 language-agnostic sorting
除了某些概念外,我觉得它们彼此非常相似.在外部排序中,它们的功能基本相同,即在k 次运行中找到最小/最大值.那么两者之间有一些显着的差异吗？
小智 2
在大多数情况下，失败者树和堆非常相似。然而，有一些重要的区别。失败者树因为它提供了每场比赛的失败者，所以将包含重复节点。由于堆是一种数据存储结构，因此它不会包含这些冗余。两者之间的另一个区别是，失败者树必须是完整二叉树（因为它是锦标赛树的一种），但堆不一定必须是二叉树。
\n\n最后，要了解失败者树的特定质量，请考虑以下问题：\n假设我们有 k 个序列，每个序列都按非降序排序，并且要按非降序合并为一个序列。这可以通过将具有最小键的元素重复传输到输出数组来实现。必须从 k 序列中的前导元素中找到最小的键。通常，这需要对每个传输的元素进行 k \xe2\x88\x92 1 次比较。然而，使用失败者树，可以将每个元素减少到 log2 k 次比较。
\n\n资料来源：《数据结构与应用手册》，Dinesh Mehta
\n