Check if x is bigger than k-th smallest number in a min-heap
algorithm, binary-heap, time-complexity
Solution
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.
Problem
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)`?