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

Question

的样品的加权中值是50％加权的百分位数（见this post @ crossvalidated for more info）/

我想知道如何一个将延伸用于查找的中值算法一串数字详细的here（有两堆，左侧为最小堆，右侧为最大堆），以便有效计算值和权重的加权中值。

我的一个想法是使用与从未加权数字流计算中位数时相同的方法，但如果权重不是一个，则只需添加额外值（例如，将插入权重为2的值两次）。然而，这不能很好地扩展到可以加倍的权重，而且看起来内存效率很低。

谢谢！

Answer 1

O（nlogn）复杂度的一种方法是将节点插入到增强平衡二叉搜索树中。树会按值排序，树中的每个节点都会增加一个赋予所有子节点总权重的字段。

成本O（logn）插入一个新的节点，包括更新所有的总重量字段。

要根据总权重的目标权重除以2来查找您下降树的中位数。此搜索将花费O（logn）。

Answer 2

我最终实现了一个使用排序数组的方法（实质上是提供最小堆的功能，但更容易搜索），并持续跟踪总权重的第50百分位。我写了a blog post about it，它有更深入的例子。