4

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!

Community
  • 1
  • 1
yuyang
  • 1,511
  • 2
  • 15
  • 40
  • @yuyang do you mean the k largest in unsorted manner because sorted would mean you can sort the array in O(n) because building heap is O(n) and sorting array in O(n) using comparison is impossible. – Vikram Bhat Mar 22 '14 at 07:58
  • 2
    Maybe you should ask this question over at cs.stackexchange.com – Niklas B. Mar 22 '14 at 17:42
  • 3
    It's due to Frederickson: http://stackoverflow.com/questions/12014892/simple-explanation-of-fredericksons-heap-selection-algorithm – David Eisenstat Mar 23 '14 at 04:16

1 Answers1

6

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

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

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.

yuyang
  • 1,511
  • 2
  • 15
  • 40
  • 4
    Do you plan to describe on a high-level how the algorithm works? That would certainly be interesting. – Niklas B. Mar 23 '14 at 19:49
  • @NiklasB. Unfortunately, the algorithm Frederickson describes is extremely hard to describe at a high level due to its complexity. His first algorithm SEL1 can be described at a high level with rigorous explanation, and it only gets more complex as he continues to revise that initial approach. – John Kurlak Sep 13 '15 at 06:49
  • I figured as much... It's also entirely impractical from what I understand. – Niklas B. Sep 13 '15 at 10:11