java

You are given an array A1..n of n different keys, and a fixed integer k. The keys of A are not sorted. Suggest an (n log k) algorithm that prepares an array B[1..n) such that for every i in the range k..n, the cell B[iwill contain the k'th smallest key in A1..). For example, if the algorithm is executed with k = 1, then B[i] (for every i) will contain the the minimum key in A[1..i). If k = 2, then Bil contains the second smallest key in B[1...). Of course, sorting A is a trivial solution to the question, but this will requires (n log n) time, which is more than O(n log k)