Real time sorting of an array

This was an interview question.

"Receives 1000 bids/second for a stock. 开发者_开发技巧Want to store the top 50 bids and calculate the mean. How?"

---

You wouldn't "real-time sort". You would probably use a heap (priority queue) data structure of the top 50 bids so far. If the next bid is above the min, then you would do a delete min, then insert the new bid. The priority queue allows you to quickly find the minimum value, delete it, and add a new value.

You can maintain the mean value by adding 1/50th of the difference between the new bid and the departing bid (only when the new bid is better than the 50th highest bid).