This question already has an answer here:

My question is something of a scheduling problem. I'd like to know what algorithm to use to find the top k items in a fixed length queue in which the values of the items change dynamically.basically a long running online top k selection

I imagine that operating systems do this all the time, but not being a systems guy, I don't know what terms to search for. Thanks in advance.


marked as duplicate by David Richerby, Wandering Logic, FrankW, Juho, Thomas Klimpel Oct 21 '14 at 5:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


The problem is known as partial sorting. Wikipedia gives various algorithms, using heaps and so on.

  • $\begingroup$ Thanks for the response.my problem is somewhat more complicated though. Simply by sitting in the queue, my values change over time. So while the number of values remains fixed, the values themselves spontaneously change, yet I still need to maintain the top k. I could repeatedly apply partial sorting, but I wonder whether there is a more efficient way to "update" the pre-existing partially sorted queue. $\endgroup$ – user20930 Oct 18 '14 at 13:57

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