I'm given a binary min-heap (implemented with an array) and need to come up with a (simple) efficient (no more than $k$ comparisons) to find the $k$-th minimal element.
My attempt was as follows:
- check who is the smallest among the root children
- scan the corresponding sub-heap maintaining a counter counting how many nodes are smaller than the larger child of the root (but larger than the smaller child). If the counter reaches $k-1$ return the value of the current node. other-wise after the scan is finished, call this method recursively on the larger root child to find the ($k$ $-$ couter_value + 1)-th minimal element of the larger child.
I just can't put this together formally and not sure this can be implemented with no more than $k$ comparisons.
Thanks for any help.