Finding all numbers in a heap which is smaller then k in linear time

Question

Given a heap, and some number k in the heap, how can I find the r numbers which are smaller then k in O(r)?

I was given an algorithm which I don't understand: Travel with pre-order on the heap, and while the values are smaller then k (and != null) print them. And supposedly this takes O(3r+1)=O(r) checkings.

Can someone explain me the solution? Thanks!

http://stackoverflow.com/questions/22574580/algorithm-for-finding-the-largest-k-numbers-in-a-max-heap-of-size-n-in-ok-time — lavin, Jul 24 '15 at 18:09

score 1 · Accepted Answer · answered Jul 24 '15 at 18:08

The only numbers you need to visit on the heap are the numbers smaller than k and their immediate children. As soon as you see a child that is too big, you know you don't need to look at its children. Each number in the heap has at most two children so this puts a limit of about 2r on the numbers you visit that you don't need (clearly r=0 is a special case).

Finding all numbers in a heap which is smaller then k in linear time

1 Answers1