Minheap的Topk

Question

如果我将数据点保存在minheap (A)中，我的应用程序效率最高。但是，作为结束步骤，我想从A输出TopK。

作为起点，从A到前面将数据点从后到前添加到另一个minheap (B)，一旦用K个数据点填充，小于根的reject数据点将以相反的顺序提供TopK列表。

我想知道我是否需要从后到前完整地遍历A，或者当我完成至少提供了K个数据点的行(意思是树的深度)时我可以停止吗？

我知道有一些算法可以将小堆转换为最大堆，但我不希望对整个原始堆进行排序，只希望对TopK进行排序。

提前感谢

Answer 1

您需要考虑底部的log_2(K)完整行。然后你就可以停止了，因为每一个离根更近的项目都小于或超过K个其他项目，并且不能在前K中。

这不会为您节省大量工作，因为堆中至少有一半的项是叶子。

Answer 2

基于%1的微堆A的N=size

我认为最有效的算法如下：

1. 使用大小为K的Minheap B使用已知的流式TopK算法来计算叶节点(N/2+1到N)的暂定TopK (例如，参见:将索引放入构成TopK的节点的A中，然后递归地检查它们的父节点以查看它们是否构成TopK。如上所述，递归深度受底部log2(K)完整行的索引的约束。

在实践中，我发现这通常会检查N/2 +K个节点，尽管退化的情况可能会一直到检查底部的log2(K)行。