2
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The minimum element will the root. So in constant time you can find the minimum element. Delete the minimum element from the root. Now min-heapify (make it minheap) the resultant tree.

The second minimum element will be the root again. Repeat the procedure mentioned above.

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.

$\endgroup$
3
  • $\begingroup$ This does not use at most $k$ comparisons in the general case (as stated in the question). $\endgroup$
    – Nathaniel
    Apr 19, 2021 at 12:24
  • $\begingroup$ One can't use at most $k$ comparisons as otherwise one can sort $n$ element in O(n) time. $\endgroup$
    – old
    Apr 19, 2021 at 12:28
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Apr 19, 2021 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.