Let A be an array of n different numbers (positive & negative).

We are interested in the ⌊log_2(n)⌋ smallest values,

and in the ⌊log_2(n)⌋ largest values.

Find algorithm which calculates this 2⌊log_2(n)⌋ values,

and presents them in a sorted array (size = 2⌊log_2(n)⌋)

1. the running time of the algorithm must be θ(n),
2. prove that the running time is θ(n).

I thought maybe heap sort can be useful, but I'm really not sure.

I don't need a code just the idea... I would appreciate any help

Thanks :) and sorry if I have English mistakes :(

CodePudding user response：

My general approach would be to to create 2 heap data structures, one for the max and one for the min, and heapify the array for/in in both of them. Heapifying is an operation of linear time complexity if done right.

Then I would extract ⌊log_2(n)⌋ items from both heaps where each extraction is of complexity O(log n). So, this would give us the following rough estimation of calculations:

2 * n   2 * (log(n))^2

2 * n for two heapifying operations. log(n) * log(n) for extracting log(n) elements from one of the heaps. 2 * (log(n))^2 for extracting log(n) elements from both heaps.

In big O terms, the ruling term is n, since log(n) even to the power of two is asymptotically smaller. So the whole expression above renders to a sweet O(n).