# Top N percent elements in a queue

I implemented a queue using two stacks which gives me $O(1)$ en-queue time, $O(1)$ amortised time. Now suppose I want to find top $10\%$ elements in the queue at any time. How am I suppose to implement it.

For example: queue takes the element in this order $$\{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 \}.$$

Top $10\%$ elements means $10 \%$ of $20 = 2$.

Hence the answer will be $19$ and $20$.

The best way I can think of is to sort it and then calculate $N%$ of size of queue and return that many elements. This takes about $O (n \log n + k)$ time.

Is this the most efficient way? I came across this algorithm. It's a linear solution. It seems like an answer, however I would like to know your views.

• Your intuition on using the linear time order statistic algorithm is correct. In your example, you want to find the 2nd largest element (algorithm in O(n)). Then you parse through the entire list one more time (O(n)), reporting all elements greater than or equal to the element previously found. – bbejot Sep 10 '14 at 19:07
• So you want faster than $O(n)$ algorithm – The Mean Square Oct 12 '14 at 5:07