在锦标赛树的实现中，额外的空间被用作要比较的数据被设置在树的叶子上然后进行比较。我读到当我们必须合并 k 个排序数组时很有帮助。现在，假设我们要合并 k 个排序数组。如果不是存储实际值，而是存储索引并创建一个最小堆，然后在 min_heap 实现中使用自定义比较器函数，该函数按该索引处的值排序。这样我们就可以知道要添加到堆中的下一个元素。这不是更好的实施，因为它可以节省我们一半的空间吗？此外，时间复杂度也将相同。上面的实现不是比锦标赛树方法更好吗？
那么，在哪些情况下锦标赛树会有所帮助？
问问题
787 次
1 回答
1
锦标赛树对于锦标赛排序很有用，它通常用于 N 路合并，有时也用于外部排序。锦标赛排序被认为是堆排序的一种变体。
另一个应用是查找多个排序数组的中位数，或查找列表中顶部（或底部）的 k 个项目。
锦标赛树不是二叉堆的替代品，而是二叉堆的特定用途。
于 2018-02-14T17:51:55.707 回答