algorithm - 从流中查找运行介质

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

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

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

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