Give an O(n + klogn) algorithm to compute the kth smallest number in a
given list of n elements. Clearly describe the steps and how much time
they take. Justify the complexity of the complete algorithm.

---

Request for Question Clarification by secret901-ga on 04 Jun 2003 00:05 PDT

Hello math01,
Do you want the algorithm given in Java or would pseudocode be OK?

---

Clarification of Question by math01-ga on 04 Jun 2003 23:38 PDT

Hi secret901-ga,

pseudocode is ok but providing the java code as well will not be bad.

Thanks

Build a (max)heap on the N elements (O(N) time)
Perform k deleteMax operations       (O(klogN) time)
The last element extracted from the heap is the answer.