algorithm - 从整数流中查找运行中位数

Question

Possible Duplicate:
Rolling median algorithm in C

Given that integers are read from a data stream. Find median of elements read so far in efficient way.

我读到的解决方案:我们可以在左侧使用最大堆来表示小于有效中位数的元素，并在右侧使用最小堆来表示大于有效中位数的元素。

处理一个传入元素后，堆中的元素个数最多相差1个元素。当两个堆包含相同数量的元素时，我们将堆的根数据的平均值作为有效中位数。当堆不平衡时，我们从包含更多元素的堆的根中选择有效中位数。

但是我们如何构造最大堆和最小堆，即我们如何知道这里的有效中位数？我认为我们会在最大堆中插入 1 个元素，然后在最小堆中插入下一个元素，依此类推所有元素。如果我在这里错了，请纠正我。

Answer 1

有许多不同的解决方案可用于从流式数据中查找运行中值，我将在答案的最后简要介绍它们。

问题是关于特定解决方案(最大堆/最小堆解决方案)的细节，下面解释了基于堆的解决方案的工作原理:

对于前两个元素，将较小的元素添加到左侧的 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

现在我将按照答案开头所 promise 的一般性地谈论这个问题。从数据流中找到运行中位数是一个棘手的问题，对于一般情况，在内存限制下有效地找到精确解可能是不可能的。另一方面，如果数据具有一些我们可以利用的特征，我们就可以开发出高效的专门解决方案。比如我们知道数据是整数类型，那么我们可以使用counting sort ，它可以给你一个常量内存常量时间算法。基于堆的解决方案是一种更通用的解决方案，因为它也可用于其他数据类型( double )。最后，如果不需要精确的中位数并且近似值就足够了，您可以尝试估计数据的概率密度函数并使用它来估计中位数。