Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Simple explanation of Frederickson's heap selection algorithm

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?

like image 239
dhruvbird Avatar asked Aug 18 '12 00:08

dhruvbird


1 Answers

Try googling "frederickson heap select".

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

like image 77
Keith Ripley Avatar answered Nov 11 '22 00:11

Keith Ripley



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!