实时排列数组

这是一个面试问题。实时排列数组

“每股收益为1000股/秒，想存储前50个出价并计算均值，怎么样？

2011-09-14 A. K.

计算所有出价的平均值还是只计算前50？ –

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

您可以通过将新出价和离开出价之间的差额的1/50相加（只有当新出价优于第50次出价时）才能保持平均值。

2011-09-14 03:20:25

只是为了澄清：在堆中找到最小值的快速方法是什么？最大值很容易，但最小值似乎涉及在某个点扫描堆（或至少是叶）。除非你切换东西，以使分钟成为堆的顶部...... – cHao

您可以定位堆，以便可以使用最大值或最小值。您正在保存50个最高值。您订购堆以便min和delete_min速度很快。如果您只有一堆可以执行delete_max的堆，则可以只存储出价的负值。 –

你认为每次更新维护堆是否可行？因为对于每次更新，我都必须先创建堆，然后通过删除50个元素来读取堆。 –

回答