Get k-th largest values [closed]

Question

I have some problem. I must add a lot of different values and just get only k-th largest in the end. How can I effectively implement that and what algorithm should I use?

Answer 1

Algorithm:

1. Create a binary maximum heap, and add each one of the first K values into the heap.

2. For each one of the remaining N-K values, if it larger than the last value in the heap:

   Put it instead of the last value, and bubble it up in order to resort the heap.

3. Extract all the (K) values from the heap into a list.

---

Complexity:

1. O(K)

2. O((N-K)×log(K))

3. O(K×log(K))

If N-K ≥ K, then the overall complexity is O((N-K)×log(K)).

If N-K < K, then the overall complexity is O(K×log(K)).