从整数流中查找运行中值
可能重复：
C中的滚动中值算法
由于整数是从数据流中读取的。 查找以有效方式阅读的元素的中位数。
解决方案我读过：我们可以在左侧使用最大堆来表示小于有效中值的元素，右侧使用最小堆来表示大于有效中值的元素。
在处理一个传入元素之后，堆中元素的数量最多相差1个元素。 当两个堆包含相同数量的元素时，我们将堆的根数据的平均值视为有效中值。 当堆不平衡时，我们从包含更多元素的堆的根部中选择有效中位数。
但是，我们将如何构建一个最大堆和最小堆，即我们如何知道这里的有效中位数？ 我认为我们会在max-heap中插入1个元素，然后在min-heap中插入下一个元素，以此类推所有元素。 纠正我如果我在这里错了。
从流式数据中找到运行中位数有很多不同的解决方案，我会在答案的最后简要地讨论它们。
问题是关于特定解决方案的细节（最大堆/分堆解决方案），以及基于堆的解决方案的工作原理如下：
对于前两个元素，在左侧的maxHeap中添加一个较小的元素，在右侧的minHeap中添加较大的一个。 然后逐个处理流数据，
Step 1: Add next item to one of the heaps
if next item is smaller than maxHeap root add it to maxHeap,
else add it to minHeap
Step 2: Balance the heaps (after this step heaps will be either balanced or
one of them will contain 1 more item)
if number of elements in one of the heaps is greater than the other by
more than 1, remove the root element from the one containing more elements and
add to the other one
然后在任何时候你可以计算这样的中位数：
If the heaps contain equal amount of elements;
median = (root of maxHeap + root of minHeap)/2
Else
median = root of the heap with more elements
现在我将在答案开始时就承诺的一般问题进行讨论。 从数据流中查找运行中值是一个棘手的问题，在一般情况下，找到一个有效的内存约束的精确解决方案可能是不可能的。 另一方面，如果数据有一些我们可以利用的特性，我们可以开发出高效的专业解决方案。 例如，如果我们知道数据是一个整数类型，那么我们可以使用计数排序，这可以给你一个恒定的记忆常量时间算法。 基于堆的解决方案是更通用的解决方案，因为它也可以用于其他数据类型（双打）。 最后，如果不需要确切的中位数并且近似值足够，那么您可以尝试估计数据的概率密度函数并使用它估计中值。
如果你不能一次把所有的东西放在内存中，这个问题变得更加困难。 堆解决方案要求您将所有元素一次保存在内存中。 在这个问题的大多数现实应用中，这是不可能的。
相反，当您看到数字时，请记住您看到每个整数的次数。 假设4个字节的整数，即2 ^ 32个存储桶或最多2 ^ 33个整数（每个整数的键和数），即2 ^ 35个字节或32GB。 它可能比这少得多，因为你不需要存储键或计数那些0的条目（即像Python中的defaultdict）。 这需要花费不变的时间来插入每个新的整数。
然后在任何时候，要找到中位数，只需使用计数来确定哪个整数是中间元素。 这需要不变的时间（尽管是一个很大的常数，但是不变）。
如果输入的方差是统计分布的（例如，正态，对数正态等），那么油藏采样是从任意长的数字流中估算百分位/中位数的合理方法。
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） - 并且这种方法在恒定的时间和内存消耗下运行。
链接地址: http://www.djcxy.com/p/83823.html