Data structure and Algo

Design of the algorithm: The algorithm needs to have an input pointer to the array [1,….,k,…,n] ,a k number (k < n) And three test points: n1<n2<n3<n.

The algorithm must go through the array in one pass and print the smallest k of the objects examined to the test points n1,n2,n3 in the array.

At any given moment, the algorithm retains(contains) only the smallest (at most) organs examined so far. In other words, the space complexity of the algorithm is Θ(K)

To do this, you must design a data structure that is limited to k organs, and supports the following actions:

insert(x)- Insert key x. The complexity of the running time Θ(logk) 1. If the structure contains less than k organs, the algorithm will insert x. 2. If the structure contains Ý‡k organs, the algorithm will insert x only if it is smaller than the max organ in the structure. In this case, the algorithm will remove the maximum organ from the structure.

printkMin() – Prints the k smallest organs examined so far. The complexity of running time Θ(K).

you may use Priority Queue as a base layer for your data structure.

Run the algorithm you designed on three arrays A, B, C in lengths of 800,400,200 respectively. Fill the arrays with a library function designed to generate random numbers; Each array will contain Organs in field 0 – 1023.

For each arrays input, run the algorithm you wrote with the values ​​k= 100,50,10 Ý‡ = and Test points n1= n/4, n2= n/2, n3 = 3n/4.