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

Question

假定从数据流中读取整数。查找迄今为止有效读取的元素的中位数。我已阅读的解决方案：我们可以在左侧使用最大堆表示小于有效中位数的元素，在右侧使用最小堆表示大于有效中位数的元素。处理传入的元素后，堆中的元素数量最多相差1个元素。当两个堆包含相同数量的元素时，我们发现堆根数据的平均值为有效中位数。当堆不平衡时，我们从包含更多元素的堆根中选择有效中位数。但是，我们将如何构造最大堆和最小堆，即我们如何知道有效中位数？我认为我们将在max-heap中插入1个元素，然后在min-heap中插入下一个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

现在，我将按照答案开头所承诺的一般性地讨论这个问题。从数据流中找到运行中位数是一个棘手的问题，并找到一个确切的解决方案与内存的限制有效地大概是不可能的一般情况。另一方面，如果数据具有我们可以利用的某些特征，那么我们可以开发有效的专用解决方案。例如，如果我们知道数据是整数类型，则可以使用计数排序，可以为您提供恒定的内存恒定时间算法。基于堆的解决方案是一种更通用的解决方案，因为它也可以用于其他数据类型（双精度）。最后，如果不需要精确的中位数并且近似值足够，则可以尝试估计数据的概率密度函数，并使用该函数估计中位数。