可能的重复: 滚动中值算法
假设整数是从数据流中读取的。以有效的方式查找到目前为止读取的元素的中位数。
我读过的解决方案:我们可以在左边使用max堆来表示小于有效中位数的元素，在右边使用min堆来表示大于有效中位数的元素。
在处理一个传入元素后，堆中的元素数量最多相差1个元素。当两个堆包含相同数量的元素时，我们发现堆根数据的平均值为有效中位数。当堆不平衡时，我们从包含更多元素的堆根中选择有效中值。
但是我们如何构造最大堆和最小堆也就是说，我们如何知道这里的有效中值?我认为我们应该在max-heap中插入1个元素然后在min-heap中插入下一个元素，如此类推。如果我说错了请指正。
当前回答
如果输入的方差是统计分布的(如正态分布、对数正态分布等)，那么从任意长的数据流中估计百分位数/中位数是一种合理的方法。
int n = 0; // Running count of elements observed so far
#define SIZE 10000
int reservoir[SIZE];
while(streamHasData())
{
int x = readNumberFromStream();
if (n < SIZE)
{
reservoir[n++] = x;
}
else
{
int p = random(++n); // Choose a random number 0 >= p < n
if (p < SIZE)
{
reservoir[p] = x;
}
}
}
“水库”则是一个运行的，均匀的(公平的)，所有输入的样本-无论大小。然后找到中位数(或任何百分位数)是一个简单的问题，即对存储库进行排序并轮询感兴趣的点。
由于存储库的大小是固定的，因此排序可以被认为是有效的O(1) -并且该方法运行的时间和内存消耗都是常数。
其他回答
一种直观的思考方法是如果你有一棵完全平衡的二叉搜索树，那么根就是中值元素，因为这里有相同数量的较大和较小的元素。 现在，如果树没有满，情况就不一样了，因为上一层中会有元素缺失。
所以我们可以用中值和两棵平衡二叉树，一棵表示小于中值的元素，另一棵表示大于中值的元素。这两棵树必须保持相同的大小。
当我们从数据流中获得一个新整数时，我们将其与中位数进行比较。如果它大于中值，我们就把它加到右边的树上。如果两个树的大小相差超过1，我们删除右边树的最小元素，使其成为新的中值，并将旧的中值放在左边树中。更小的也一样。
你不能只用一个堆来做这个吗?更新:没有。请看评论。
不变性:在读取2*n个输入后，最小堆保存其中最大的n个。
循环:读取2个输入。将它们都添加到堆中，并删除堆的最小值。这将重新建立不变量。
所以当读取了2n个输入时，堆的最小值是第n大的。在中间位置附近取两个元素的平均值，以及在奇数个输入之后处理查询，需要稍微复杂一点。
如果您不能一次将所有项保存在内存中，这个问题就会变得更加困难。堆解决方案要求您一次将所有元素保存在内存中。这在这个问题的大多数实际应用中是不可能的。
相反，当您看到数字时，请记录您看到每个整数的次数。假设4个字节整数，即2^32个桶，或最多2^33个整数(每个int的key和count)，即2^35字节或32GB。它可能会比这个小得多，因为您不需要存储键或为那些为0的条目计数(例如。就像python中的defaultdict)。插入每个新整数需要常数时间。
然后在任意点，要找到中位数，只需使用计数来确定哪个整数是中间元素。这需要常数时间(虽然是一个很大的常数，但仍然是常数)。
高效这个词取决于上下文。这个问题的解决方案取决于执行的查询量与插入量的关系。假设你插入N个数字K次直到最后你对中位数感兴趣。基于堆的算法的复杂度是O(N log N + K)。
考虑下面的替代方案。将数字放入一个数组中，对于每个查询，运行线性选择算法(比如使用快速排序枢轴)。现在你有了一个运行时间为O(K N)的算法。
现在如果K足够小(不频繁查询)，后一种算法实际上更有效，反之亦然。
如果输入的方差是统计分布的(如正态分布、对数正态分布等)，那么从任意长的数据流中估计百分位数/中位数是一种合理的方法。
int n = 0; // Running count of elements observed so far
#define SIZE 10000
int reservoir[SIZE];
while(streamHasData())
{
int x = readNumberFromStream();
if (n < SIZE)
{
reservoir[n++] = x;
}
else
{
int p = random(++n); // Choose a random number 0 >= p < n
if (p < SIZE)
{
reservoir[p] = x;
}
}
}
“水库”则是一个运行的，均匀的(公平的)，所有输入的样本-无论大小。然后找到中位数(或任何百分位数)是一个简单的问题，即对存储库进行排序并轮询感兴趣的点。
由于存储库的大小是固定的，因此排序可以被认为是有效的O(1) -并且该方法运行的时间和内存消耗都是常数。
