可能重复：
C 中的滚动中值算法
鉴于整数是从数据流中读取的。以有效的方式查找到目前为止读取的元素的中位数。
我读过的解决方案：我们可以在左侧使用最大堆来表示小于有效中位数的元素，在右侧使用最小堆来表示大于有效中位数的元素。
处理传入元素后，堆中的元素数量最多相差 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
现在我将按照答案开头所承诺的一般性地讨论这个问题。从数据流中找到运行中位数是一个棘手的问题，对于一般情况来说，有效地找到具有内存限制的精确解决方案可能是不可能的。另一方面，如果数据具有我们可以利用的某些特征，我们可以开发有效的专业解决方案。例如，如果我们知道数据是整数类型，那么我们可以使用计数排序，它可以给你一个常数记忆常数时间算法。基于堆的解决方案是一种更通用的解决方案，因为它也可以用于其他数据类型（双精度）。最后，如果不需要确切的中位数并且近似值就足够了，您可以尝试估计数据的概率密度函数并使用它估计中位数。
如果输入的方差是统计分布的（例如正态分布、对数正态分布等），则储层采样是从任意长的数字流中估计百分位数/中位数的合理方法。
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) - 这种方法在恒定时间和内存消耗下运行。
如果您不能一次将所有项目都保存在内存中，那么这个问题就会变得更加困难。堆解决方案要求您一次将所有元素保存在内存中。这在这个问题的大多数实际应用中是不可能的。
相反，当您看到数字时，请跟踪您看到每个整数的次数。假设 4 字节整数，即 2^32 个桶，或最多 2^33 个整数（每个 int 的键和计数），即 2^35 字节或 32GB。它可能会比这少得多，因为您不需要为那些为 0 的条目存储密钥或计数（即，就像 python 中的 defaultdict）。这需要恒定的时间来插入每个新整数。
然后在任何时候，要找到中位数，只需使用计数来确定哪个整数是中间元素。这需要恒定的时间（尽管是一个很大的常数，但仍然是常数）。
我发现计算流百分位数的最有效方法是 P² 算法：Raj Jain，Imrich Chlamtac：在不存储观测值的情况下动态计算分位数和直方图的 P² 算法。交流。ACM 28（10）：1076-1085（1985）
该算法很容易实现并且运行良好。但是，这是一个估计值，因此请记住这一点。从摘要：
提出了一种启发式算法，用于动态计算中位数和其他分位数。在生成观测值时动态生成估计值。不存储观察结果；因此，无论观察次数如何，该算法的存储需求都非常小且固定。这使其非常适合在可用于工业控制器和记录器的分位数芯片中实现。该算法进一步扩展到直方图绘制。分析算法的准确性。
如果我们想找到最近看到的n 个元素的中位数，这个问题有一个精确的解决方案，只需要将n 个最近看到的元素保存在内存中。它速度快且扩展性好。
可索引的跳过列表支持 O(ln n) 插入、删除和索引搜索任意元素，同时保持排序顺序。当与跟踪第 n 个最旧条目的FIFO 队列结合使用时，解决方案很简单：
class RunningMedian:
'Fast running median with O(lg n) updates where n is the window size'
def __init__(self, n, iterable):
self.it = iter(iterable)
self.queue = deque(islice(self.it, n))
self.skiplist = IndexableSkiplist(n)
for elem in self.queue:
self.skiplist.insert(elem)
def __iter__(self):
queue = self.queue
skiplist = self.skiplist
midpoint = len(queue) // 2
yield skiplist[midpoint]
for newelem in self.it:
oldelem = queue.popleft()
skiplist.remove(oldelem)
queue.append(newelem)
skiplist.insert(newelem)
yield skiplist[midpoint]
以下是完整工作代码的链接（易于理解的类版本和内联可索引跳过列表代码的优化生成器版本）：
一种直观的思考方式是，如果你有一个完全平衡的二叉搜索树，那么根将是中间元素，因为会有相同数量的更小和更大的元素。现在，如果树没有满，情况就不是这样了，因为最后一层会缺少元素。
所以我们可以做的是有中位数和两棵平衡二叉树，一棵用于小于中位数的元素，一棵用于大于中位数的元素。两棵树必须保持相同的大小。
当我们从数据流中获得一个新整数时，我们将它与中位数进行比较。如果它大于中位数，我们将它添加到正确的树中。如果两棵树的大小相差超过 1，我们删除右树的最小元素，使其成为新的中值，并将旧的中值放入左树。同样适用于较小的。
高效是一个取决于上下文的词。此问题的解决方案取决于相对于插入量执行的查询量。假设您在对中位数感兴趣的最后插入 N 个数字和 K 次。基于堆的算法的复杂度为 O(N log N + K)。
考虑以下替代方案。插入数组中的数字，并为每个查询运行线性选择算法（例如，使用快速排序枢轴）。现在你有了一个运行时间为 O(KN) 的算法。
现在，如果 K 足够小（不经常查询），则后一种算法实际上更有效，反之亦然。
这是我的简单但有效的算法（在 C++ 中），用于从整数流中计算运行中位数：
#include<algorithm>
#include<fstream>
#include<vector>
#include<list>
using namespace std;
void runningMedian(std::ifstream& ifs, std::ofstream& ofs, const unsigned bufSize) {
if (bufSize < 1)
throw exception("Wrong buffer size.");
bool evenSize = bufSize % 2 == 0 ? true : false;
list<int> q;
vector<int> nums;
int n;
unsigned count = 0;
while (ifs.good()) {
ifs >> n;
q.push_back(n);
auto ub = std::upper_bound(nums.begin(), nums.end(), n);
nums.insert(ub, n);
count++;
if (nums.size() >= bufSize) {
auto it = std::find(nums.begin(), nums.end(), q.front());
nums.erase(it);
q.pop_front();
if (evenSize)
ofs << count << ": " << (static_cast<double>(nums[nums.size() / 2 - 1] +
static_cast<double>(nums[nums.size() / 2]))) / 2.0 << '\n';
else
ofs << count << ": " << static_cast<double>(nums[nums.size() / 2]);
}
}
}
指定数字序列的bufferSize大小，必须在其上计算运行中位数。从输入流中读取数字时ifs，大小的向量bufferSize按排序顺序维护。中位数的计算方法是取排序向量的中间，如果bufferSize是奇数，或者两个中间元素的和除以 2，如果bufferSize是偶数。另外，我维护了一个bufferSize从输入中读取的最后一个元素的列表。添加新元素时，我将其放在已排序向量中的正确位置，并从向量中删除添加的元素bufferSize步骤之前（保留在列表前面的元素的值）。同时我从列表中删除旧元素：每个新元素都放在列表的后面，每个旧元素都从前面删除。到达 之后，列表和向量都停止增长，并且每次插入新元素都会通过删除之前放置在列表步骤bufferSize中的旧元素来补偿。bufferSize请注意，我不关心我是否从向量中删除了元素、bufferSize之前放置的步骤，或者只是一个具有相同值的元素。对于中位数的值，这无关紧要。所有计算的中值都在输出流中输出。
你不能只用一个堆做这个吗？更新：没有。见评论。
不变：读取2*n输入后，最小堆拥有其中n最大的。
循环：读取 2 个输入。将它们都添加到堆中，并删除堆的最小值。这重新建立了不变量。
所以当2n输入被读取时，堆的最小值是第 n 大的。需要一些额外的复杂性来平均中间位置周围的两个元素并在奇数个输入后处理查询。