假定从数据流中读取整数。查找迄今为止有效读取的元素的中位数。
我已阅读的解决方案：我们可以在左侧使用最大堆表示小于有效中位数的元素，在右侧使用最小堆表示大于有效中位数的元素。
处理传入的元素后，堆中的元素数量最多相差1个元素。当两个堆包含相同数量的元素时，我们发现堆根数据的平均值为有效中位数。当堆不平衡时，我们从包含更多元素的堆根中选择有效中位数。
但是，我们将如何构造最大堆和最小堆，即我们如何知道有效中位数？我认为我们将在max-heap中插入1个元素，然后在min- heap中插入下一个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
现在，我将按照答案开头所承诺的一般性地讨论这个问题。从数据流中找到运行中位数是一个难题，对于一般情况而言，有效地找到具有内存限制的 精确解决方案 可能是不可能的。另一方面，如果数据具有我们可以利用的某些特征，那么我们可以开发有效的专用解决方案。例如，如果我们知道数据是整数类型，则可以使用计数排序，这可以为您提供恒定的内存恒定时间算法。基于堆的解决方案是一种更通用的解决方案，因为它也可以用于其他数据类型（双精度）。最后，如果不需要精确的中位数并且近似值足够，则可以尝试估计数据的概率密度函数，然后使用该函数估计中位数。
