algorithm - 数组的实时排序

Question

这是一道面试题。

“接收 1000 个股票/秒的出价。想要存储前 50 个出价并计算平均值。如何？”

Answer 1

你不会“实时排序”。到目前为止，您可能会使用前 50 个出价的堆（优先队列）数据结构。如果下一个出价高于最低出价，那么您将执行删除最低出价，然后插入新出价。优先级队列允许您快速找到最小值、删除它并添加一个新值。

您可以通过增加新出价和离开出价之间差值的 1/50 来保持平均值（仅当新出价优于第 50 个最高出价时）。