用于在大小为N的最大堆中找到最大K数的O(K*logK)算法是众所周知的.我听说有一个O(K)算法来解决这个问题.我没有找到关于此的文献.任何人都可以对此提出任何指示吗？谢谢!
我终于找到了描述该算法的论文.Quora上有一个类似的问题.
论文," 一种优化算法选择在最小堆 ",由GN弗雷德里克森,介绍了算法.以下是摘要:
提出了一种O(k)时算法,用于选择大小为nk的二进制最小堆中的第k个最小元素.该方法使用递归定义的数据结构,该结构对堆中的某些元素施加分层分组.该结果建立了部分次序的另一个例子,其中第k个最小元素可以在时间上与信息理论下限成比例地确定.确定了资源分配问题和k个最小生成树的枚举的两个应用.