Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top
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.
The minimum element will the root. So in constant time you can 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 $k$th minimum element in time $O(k log n)$ where $n$ is the number of elements in the given min healp.