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.