I know this question was asked before. I read the following question: how to determine if the kth largest element of the heap is greater than x but I have further questions. I did not want to post in a thread that old. So:
Given a number x and a number k, check if x is bigger than the k-th smallest element in O(k).
The previous question does the same thing, but with max-heaps and smaller than. That is not the problem.
Consider a binary min-heap:
1
2 3
12 17 50 90
23,18 80,88 51,52 91,92
Let x be 19 and k be 6.
The 6th smallest element is 18.
If I do the algorithm in the other thread, it would check as follows:
1+,2+,12+,23,18+,17+,80,88,3+
The + signals when the counter is increased.
How does the algorithm know that 18 is the k-th smallest number, not 3?
And why does the checking of 23, 80 and 88 not interfere with O(k)?
How does the algorithm know that 18 is the kth smallest number, not 3?
It doesn't matter to the algorithm - it simply counts the smaller numbers - it doesn't keep track of which one is the k-th smallest number.
If it finds more than k smaller numbers, it knows the k-th smallest number is smaller than x.
If we want to actually find the k-th smallest number, we'd likely need to do O(k log k) work, as we need to keep track of the candidates in order so we know which one is in the k-th position, or we could do an (expected) O(n) quickselect.
And why does the check of 13,80,88 not interfere with O(k)?
Think of it this way - each node only has 2 children, and we'll only process a node's children if it's smaller than x, so we can include 23 and 18 in 12's running time (we do a constant amount of work for 12, including the work involved for 23 and 18) and 17 in 2's running time.