在大小为N的最大堆中找到最大K个数的O（K*logK）算法是众所周知的。我听说有一个O（K）算法可以解决此问题。我找不到有关此的文献。有人可以对此提出任何建议吗？谢谢！
我终于找到描述该算法的论文。关于Quora也有类似的问题。
GN Frederickson 的论文“ 用于最小堆中的最佳选择算法 ”描述了该算法。以下是摘要：
提出了一种O（k）时间算法，用于选择大小为n⪢k的二进制最小堆中的第k个最小元素。该方法使用递归定义的数据结构，这些数据结构对堆中的某些元素施加了分层分组。结果建立了偏序的另一个示例，对于该偏阶，可以在时间上确定与信息论下限成比例的第k个最小元素。确定了两个应用程序，分别用于资源分配问题和k个最小生成树的枚举。
