# Given a binary min-heap, find the $k$-th element

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:

1. check who is the smallest among the root children
2. 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.

By this procedure, you will find $$k$$-th minimum element in time $$O(k \log n)$$ where $$n$$ is the number of elements in the given min-heap.
• This does not use at most $k$ comparisons in the general case (as stated in the question). Apr 19 at 12:24
• One can't use at most $k$ comparisons as otherwise one can sort $n$ element in O(n) time.
• This is not clear, as you would need $O(\sum\limits_{k=1}^n k) = O(n^2)$ comparisons to sort $n$ elements. If you think that's the case, please explain why in your answer. Apr 19 at 12:33