Simple explanation of Frederickson's heap selection algorithm

Question

Is there any simple explanation of Frederickson's heap selection algorithm to find the k'th ranked element in O(k) time in a min-heap available anywhere online? If not, can anyone explain the gut of the algorithm?

Baxley

Answer 1

Try googling "frederickson heap select".

http://160592857366.free.fr/joe/ebooks/ShareData/An%20Optimal%20Algorithm%20for%20Selection%20in%20a%20Min-Heap.pdf

Greenback

I wanted something that explained the core of the algorithm in a page or 2 rather than 27 pages. – Baxley

The core of the algorithm is described in about a page or two starting on page 17. – Greenback

This link appears to be dead. Can you find an updated version? – Ponytail

@templatetypedef: 160592857366.free.fr/joe/ebooks/ShareData/… – Galvanotropism