快速中位数更新的算法

Question

假设在某一时刻，您有一个包含N个数字并知道中位数M的集合。现在，您有一个新值X，可能需要更新M。（假设您处理的数字都是唯一的。此外，所有样本都是串行接收的，因此不存在并发问题。）

计算新平均值很简单：取旧平均值，加上X，乘以N，然后除以N + 1。（从检查N个元素的平均值如何定义可以清楚地看出这一点。目前我对数字不太担心。）

我的问题是：有人能提出一个创意/新颖（或者证明最优）的方法来解决更新中位数的问题吗？下面是一个例子（我自己设计的简单想法），带有一些分析：

在此示例中，我将使用std::forward_list，因为C++11是我最近遇到的。不失一般性，我假设您正在正确地进行操作：维护一个已排序的元素列表（类型T），std::forward_list 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)方法很糟糕/您的方法要好得多，您不必评论它，我只是建议它作为一个起点。

- hagemt

---

你可以在O(log(n))时间内完成。将元素添加到平衡二叉树和选择第k大的元素都是O(log(n))时间操作。如果想尝试更有趣的东西，也许可以尝试使用两个堆，一个用于n/2个最大元素，另一个用于最小元素。 - Marc Glisse

@MarcGlisse：看看我的答案，你不必搜索第k大的元素，因为你已经知道它或者是第(k+1)大或第(k-1)大的元素 :-) - Arne Mertz

@SauceMaster，看起来你正在跟踪列表中出现最多的元素。那不是中位数。 - Arne Mertz

@ArneMertz：哈哈，没错。那绝对是模式。抱歉！ - AndyG

Answer 1

您可以将数组分成两个相等大小的堆树，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)时交换它们的顶部。

- Vovanium

Answer 2

您可以使用std::set, 并且插入元素不会使迭代器失效。

如果N是奇数，您可以将迭代器mIt保持在集合的中位数元素上；如果N是偶数，您可以将其保持在两个中位数元素的左侧。

让我们考虑在插入元素时可能发生的不同情况：

当N是奇数时插入：如果插入的元素比*mIt小，则旧中位数变为两个新中位数的右侧，因此要将迭代器减1。如果它比*mIt大（或对于multiset来说相等），则一切正常。

当N是偶数时插入：如果插入的元素比*mIt大（或相等），则旧右中位数成为中位数，因此要将迭代器加1。如果它比*mIt小，则旧左中位数成为中位数，一切正常。

template <class T>
class MedianHolder {
  std::set<T> elements;
  std::set<T>::const_iterator mIt;

public:
  T const& getMedian() const { return *mIt; }

  void insert(T const& t) {
    if (elements.empty()) {
      mIt = elements.insert(t).first;
      return;
    }

    bool smaller = std::less<T>(t,getMedian());
    bool odd = (elements.size() % 2) == 1;

    if (!elements.insert(t).second)
      return; //not inserted

    if (odd && smaller) --mIt;
    else if (!odd && !smaller) ++mIt;
  }
};

我会把擦除元素的任务留给您作为练习；-)

- Arne Mertz

---

优秀的解决方案！如果您的应用程序可能会多次产生相等的元素，那么请记住使用multiset。否则，例如序列 1 2 3 1 1 1 1 1 的“中位数”将显示为“2”，而不是（正确的）“1”。 - n0dus