从值和权重流中查找运行加权中值

Question

样本的加权中值是50%的加权百分位数(更多信息请参见本文@ cross validated )/

我想知道如何扩展算法，以从< code>double值和权重的流中有效地计算加权中值，该算法用于查找此处详述的运行数字流的中值(有两个堆，左边是min堆，右边是max堆)。

我的一个想法是使用与从未加权的数字流计算中位数相同的方法，但如果权重不是一，只需输入额外的值（例如，权重为2的值将入两次）。但是，这不能很好地扩展可以加倍的权重，并且似乎记忆效率低下。

谢谢

Answer 1

我最终实现了一种方法，该方法使用排序数组（基本上起到最小堆的作用，但搜索更容易），并持续跟踪总权重的第50个百分位。我写了一篇关于它的博客文章，其中有更深入的例子。

Answer 2

一种具有O(nlogn)复杂度的方法是将节点插入到增强的平衡二叉查找树中。树将按值排序，树中的每个节点将通过一个给出所有子节点总权重的字段来扩充。

插入包括更新所有总权重字段的新节点需要O（logn）。

要查找中间值，您可以根据总权重除以2的目标权重来下降树。此搜索将采用O（logn）。