3. You are given an array A[1..n) of n different keys, and a fixed integer k. The keys of A are not sorted Suggest an O(n log k) algorithm that prepares an array B1..n such that for every i in the range k..n, the cell Bi) will contain the k'th smallest key in A[1..i). For example, if the algorithm is executed with k = 1, then B[i] (for every i) will contain the minimum key in A[1...). If k = 2, then B[i] contains the second smallest key in A[1...). See Figure 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). Example (k = 2) i: A: B: 1 20 - 2 10 20 3 30 20 4 5 10 5 17 10 6 2 5 Table 1: Example for question 3 for the case k = 2. B[4) is 10, since amongst the keys in A(1.4) (that is, 20,10,30,5), the second smallest key 10. B[6] = 5 since amongst the number A[1..6] (20,10,30,5,17, 2), the smallest is 2 and the second smallest is 5. 3. You are given an array A[1..n) of n different keys, and a fixed integer k. The keys of A are not sorted Suggest an O(n log k) algorithm that prepares an array B1..n such that for every i in the range k..n, the cell Bi) will contain the k'th smallest key in A[1..i). For example, if the algorithm is executed with k = 1, then B[i] (for every i) will contain the minimum key in A[1...). If k = 2, then B[i] contains the second smallest key in A[1...). See Figure 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). Example (k = 2) i: A: B: 1 20 - 2 10 20 3 30 20 4 5 10 5 17 10 6 2 5 Table 1: Example for question 3 for the case k = 2. B[4) is 10, since amongst the keys in A(1.4) (that is, 20,10,30,5), the second smallest key 10. B[6] = 5 since amongst the number A[1..6] (20,10,30,5,17, 2), the smallest is 2 and the second smallest is 5