Develop an algorithm that computes the k th smallest element

Develop an algorithm that computes the k th smallest element of a set of n distinct integers in O(n + k log n) time.

Please HELP and don\'t post irrelative answer. Thank you!

Solution

Algorithm : (To find kth smallest element)

1)build a min heap (build min heap method , all elements at a time )// for this complexity would be O(n)

2)we know that the root of min heap is minimum among all other elements, hence we have to extract min for k times(until we got the kth element) ..

the complextiy of extract min is log n,(n is number of nodes in heap)

we extracting k mins for finding kth min, hence the complexity for extracting k mins in k*logn

The total complexity of algorithm : O(n+k*log n)