算法发现的大小为N最大堆最大的K个为O（K）的时间？ [英] Algorithm for finding the largest K numbers in a max heap of size N in O(K) time?

问题描述

的<一个href="http://stackoverflow.com/questions/11209556/print-the-biggest-k-elements-in-a-given-heap-in-oklogk">O(K *的logK）算法以寻找最大K个在大小为N最大堆是众所周知的。我听说，有一个O（K）算法来解决这个问题。我不觉得这个文献。任何人都可以给这个任何指针？谢谢！

The O(K * logK) algorithm for finding the largest K numbers in a max heap of size N is well known. I heard about that there is an O(K) algorithm for solving this problem. I do not find the literature on this. Could anyone give any pointers on this? Thanks!

推荐答案

我终于发现，描述了算法的纸张。有关于<一个类似的问题href="http://www.quora.com/Data-Structures/Given-a-min-heap-of-N-elements-is-it-possible-to-retrieve-the-K-smallest-elements-of-the-heap-in-O-K-time"相对=nofollow> Quora的。

I finally find the paper that describes the algorithm. There is a similar question on Quora.

该文件，的优化算法选择在闽堆 ，由GN弗雷德里克森，描述的算法。以下是摘要：

The paper, "An Optimal Algorithm for Selection in a Min-Heap", by G.N. Frederickson, describes the algorithm. The following is the abstract:

这是O（K） - 时间的算法是psented为二进制最小堆大小n⪢k中选择第k个最小元素$ P $。该方法使用递归定义的数据结构中要求在堆中的某些元素的层次分组。结果建立的部分顺序的量，第k个最小的元素可以在时间正比于信息理论下限来确定进一步的例子。两个应用程序，以一个资源分配问题和第k最小生成树的枚举，识别

An O(k)-time algorithm is presented for selecting the kth smallest element in a binary min-heap of size n⪢k. The approach uses recursively defined data structures that impose a hierarchical grouping on certain elements in the heap. The result establishes a further example of a partial order for which the kth smallest element can be determined in time proportional to the information theory lower bound. Two applications, to a resource allocation problem and to the enumeration of the k smallest spanning trees, are identified.

这篇关于算法发现的大小为N最大堆最大的K个为O（K）的时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！