c++ - 快速中值更新算法

Question

假设在某个时间点，您有一个 N 个数字的集合，并且知道中位数元素: M 。现在，您获得了一个新值 X ，因此您可能需要更新 M 。 (或者更确切地说，假设您要处理的数字都是唯一的，您将需要这样做。此外，所有样本都是按顺序接收的，因此并发性没有问题。)

计算新平均值很简单:采用旧平均值，加上 X ，乘以 N ，然后除以 N + 1 。 (通过检查如何定义 N 个元素的平均值可以清楚地看出这一点。目前我不太担心数字。)

我的问题是:任何人都可以提出一种创造性/新颖(或者可能是可证明的最优)方法来解决更新中位数的问题吗？我将在下面提供一个示例(我自己设计的简单想法)，并进行一些分析:

在此示例中，我将使用 std::forward_list ，因为 C++11 是我最近遇到的地方。在不失一般性的情况下，我将假设您正在以正确的方式进行此操作:维护到目前为止遇到的元素(T 类型)的有序列表，std::forward_list<T> sorted; 当 T x; 出现时，只需使用以下方法将其折叠到位:

sorted.merge(std::forward_list<T> {{ x }});

顺便说一句，我很好奇是否有人对此有更好(更高效/优雅)的方法。欢迎提示。

因此，X 现在是 sorted 的一部分，简而言之，这是我的想法:

auto it = sorted.begin(), itend = sorted.end();
typename std::forward_list<T>::size_type count = std::distance(it, itend);
for (const auto &e : sorted) {
    if (it == itend || ++it == itend) {
        M = (count % 2) ? e : (e + M) / 2;
        break;
    } else { ++it; }
}

这里发生的一件好事(如果不是很难看的话)是:因为你将迭代器向前移动两次(并且安全地，我可能会添加，尽管以两次比较为代价)对于每个元素，当 end() 是达到，我们将处于适当的(中值)值。如果有奇数个元素，M 就是那个样本，如果不是，它只是这个元素和旧的(推出的)中位数的平均值。因为奇数和偶数交替出现，旧的或新的 M 实际上将在集合中。这个推理是合理的，是吗？

如果您认为我的 O(3n) 方法很垃圾/您的方法要好得多，则无需评论它；我只是建议将其作为起点。

Answer 1

你可以将你的数组拆分为两个 heap 树，大小相等，I 是最小的部分或数组，S 是最大的部分，它们的顶部包含最大和最小元素。假设数组 1, 2, 4, 4, 5, 5, 7, 8, 8, 8 组织如下:

 1 4
 \ /
  4   2
   \ /
    5  <--- I's top

    5  <--- S's top
   / \
  7   8
 / \
 8 8

注意，如果元素个数是偶数，则中位数 = top(S)+top(I)，如果是奇数，则其中一个堆应该比另一个堆大一个元素，而中位数在更大的元素之上。

完成后更新中位数就很简单了，你应该将你的元素添加到其中一个堆中，如果 top(S) 变得小于 top(I) 则交换它们的顶部。