algorithm - 从值和权重流中查找运行加权中位数

Question

样本的加权中位数是 50% 的加权百分位数(参见 this post @ crossvalidated for more info )/

我想知道如何扩展用于查找正在运行的数字流的中位数的算法详细 here (有两个堆，左侧是最小堆，右侧是最大堆)从 double 值和权重流中有效地计算加权中位数。

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

谢谢!

Answer 1

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

插入一个新节点包括更新所有总权重字段的成本为 O(logn)。

要查找中位数，您可以根据总重量除以 2 的目标重量降低树。此搜索将花费 O(logn)。