你不能只用一个堆来做这个吗?更新:没有。请看评论。

不变性:在读取2*n个输入后，最小堆保存其中最大的n个。

循环:读取2个输入。将它们都添加到堆中，并删除堆的最小值。这将重新建立不变量。

所以当读取了2n个输入时，堆的最小值是第n大的。在中间位置附近取两个元素的平均值，以及在奇数个输入之后处理查询，需要稍微复杂一点。

如果您不能一次将所有项保存在内存中，这个问题就会变得更加困难。堆解决方案要求您一次将所有元素保存在内存中。这在这个问题的大多数实际应用中是不可能的。

相反，当您看到数字时，请记录您看到每个整数的次数。假设4个字节整数，即2^32个桶，或最多2^33个整数(每个int的key和count)，即2^35字节或32GB。它可能会比这个小得多，因为您不需要存储键或为那些为0的条目计数(例如。就像python中的defaultdict)。插入每个新整数需要常数时间。

然后在任意点，要找到中位数，只需使用计数来确定哪个整数是中间元素。这需要常数时间(虽然是一个很大的常数，但仍然是常数)。

你不能只用一个堆来做这个吗?更新:没有。请看评论。

不变性:在读取2*n个输入后，最小堆保存其中最大的n个。

循环:读取2个输入。将它们都添加到堆中，并删除堆的最小值。这将重新建立不变量。

所以当读取了2n个输入时，堆的最小值是第n大的。在中间位置附近取两个元素的平均值，以及在奇数个输入之后处理查询，需要稍微复杂一点。

我发现的最有效的计算流百分位数的方法是P²算法:Raj Jain, Imrich Chlamtac:不存储观测数据的动态计算分位数和直方图的P²算法。Commun。Acm 28(10): 1076-1085 (1985)

该算法易于实现，工作效果非常好。然而，这只是一个估计，所以要记住这一点。来自摘要:

A heuristic algorithm is proposed for dynamic calculation qf the median and other quantiles. The estimates are produced dynamically as the observations are generated. The observations are not stored; therefore, the algorithm has a very small and fixed storage requirement regardless of the number of observations. This makes it ideal for implementing in a quantile chip that can be used in industrial controllers and recorders. The algorithm is further extended to histogram plotting. The accuracy of the algorithm is analyzed.

一种直观的思考方法是如果你有一棵完全平衡的二叉搜索树，那么根就是中值元素，因为这里有相同数量的较大和较小的元素。 现在，如果树没有满，情况就不一样了，因为上一层中会有元素缺失。

所以我们可以用中值和两棵平衡二叉树，一棵表示小于中值的元素，另一棵表示大于中值的元素。这两棵树必须保持相同的大小。

当我们从数据流中获得一个新整数时，我们将其与中位数进行比较。如果它大于中值，我们就把它加到右边的树上。如果两个树的大小相差超过1，我们删除右边树的最小元素，使其成为新的中值，并将旧的中值放在左边树中。更小的也一样。

高效这个词取决于上下文。这个问题的解决方案取决于执行的查询量与插入量的关系。假设你插入N个数字K次直到最后你对中位数感兴趣。基于堆的算法的复杂度是O(N log N + K)。

考虑下面的替代方案。将数字放入一个数组中，对于每个查询，运行线性选择算法(比如使用快速排序枢轴)。现在你有了一个运行时间为O(K N)的算法。

现在如果K足够小(不频繁查询)，后一种算法实际上更有效，反之亦然。