algorithm - Check if x is bigger than k-th smallest number in a min-heap -

i know question asked before. read following question: how determine if kth largest element of heap greater x have further questions. did not want post in thread old. so:

given number x , number k, check if x bigger k-th smallest element in o(k).

the previous question same thing, max-heaps , smaller than. not problem.

consider binary min-heap:

              1       2               3   12    17         50  90 23,18 80,88      51,52 91,92 

let x 19 , k 6.

the 6th smallest element 18.

if algorithm in other thread, check follows:

1+,2+,12+,23,18+,17+,80,88,3+ 

the + signals when counter increased.

how algorithm know 18 k-th smallest number, not 3?

and why checking of 23, 80 , 88 not interfere o(k)?

how algorithm know 18 kth smallest number, not 3?

it doesn't matter algorithm - counts smaller numbers - doesn't keep track of 1 k-th smallest number.

if finds more k smaller numbers, knows k-th smallest number smaller x.

---

if want find k-th smallest number, we'd need o(k log k) work, need keep track of candidates in order know 1 in k-th position, or (expected) o(n) quickselect.

and why check of 13,80,88 not interfere o(k)?

think of way - each node has 2 children, , we'll process node's children if it's smaller x, can include 23 , 18 in 12's running time (we constant amount of work 12, including work involved 23 , 18) , 17 in 2's running time.