从流中找到运行媒体

Question

问题：假定整数是从数据流中读取的。以有效的方式查找到目前为止读取的元素的中值。

我找到了解决方案here

我的问题是为什么我们需要使用堆而不是简单地将数字添加到向量中？

例如，假设我们使用向量来存储传入的数据，那么我们调用计算中位数的方法如下：

if vector size is even
   return (element at size/2 + element at size/2-1);
else
   return (element at size/2);

以上解决方案行得通吗？

Answer 1

如果向量中的元素顺序不对，您的解决方案将无法工作。并且如果你在vector的末尾添加元素，它们将不会按顺序排列。

另一方面，堆中的元素是有序的。

此外，第一个 return 语句中缺少除以二的部分。

Answer 2

您提出的解决方案未被广泛使用至少有两个原因：

一般来说，如果您正在处理数据流，那么假设该流很大甚至是无限的，因此存储所有值是不切实际的。
正如@ChronoTrigger 所说，您必须对矢量进行排序才能使用它。该问题通常假设您希望能够在新数据流输入时一遍又一遍地询问中位数。为了使用您的解决方案做到这一点，您必须一遍又一遍地对向量进行排序，这会很慢。

总的来说，很难有效地保持流式数据集的准确中值。有许多算法可以做到这一点，但它们都会做出权衡，例如降低准确性以降低内存使用率等。

Answer 3

只有当您将新元素添加到适当的位置（根据排序顺序）时，Vector 才会起作用。

例如：流：8 3 4 1 10 12

如果你一直在向量的末尾添加元素，则每一步的中位数：

step 1: vector: 8 median: 8
step 2: vector: 8, 3 median: (8+3)/2
step 3: vector: 8, 3, 4 median: 3 (when actually it should be 4)

希望你明白了

finding running medium from a stream