2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – bbejot
    Sep 10, 2014 at 19:07
  • $\begingroup$ So you want faster than $O(n)$ algorithm $\endgroup$ Oct 12, 2014 at 5:07

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.