Top N percent elements in a queue

Question

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.

Answer 1

You can implement this in O(klogk + n) time complexity.

Maintain an external min-heap while iterating the queue. The min-heap shall have at most k elements at a time.

Insert the first k elements in the min-heap. Thereafter compare the present queue element with the top of the heap. If the top is less than present value then delete the top element from the heap and insert this new present element.

At the end the heap shall contain top k elements in the queue.