Найти работает взвешенную медиану из потока значений и весов

Question

Взвешенной медиана выборки составляет 50% взвешенный процентиль (см this post @ crossvalidated for more info)/

мне было интересно, как можно было бы расширить алгоритм, используемый, чтобы найти медиану бегущий поток чисел, подробный here (с двумя кучами, кучей минут для левой стороны и максимальной кучей для правой стороны), чтобы эффективно вычислять взвешенную медиану из потока значений double и веса.

Одна из моих идей заключалась в том, чтобы использовать тот же метод, что и при вычислении медианы из невзвешенного потока чисел, но просто вводить дополнительные значения, если веса не являются одними (например, значение с весом 2 будет вставлено дважды). Однако это не очень хорошо масштабируется с весами, которые могут быть удвоены, а также, по-видимому, неэффективны.

Спасибо!

Answer 1

Одним из подходов с сложностью O (nlogn) было бы вставить узлы в расширенное сбалансированное двоичное дерево поиска. Дерево будет сортироваться по значению, и каждый узел в дереве будет дополнен областью, которая дала общий вес всех дочерних узлов.

Он стоит O (logn), чтобы вставить новый узел, включая обновление всех полей общего веса.

Для поиска медианы вы спускаетесь по дереву на основе целевого веса общего веса, деленного на 2. Этот поиск займет O (logn).

Answer 2

Я закончил реализацию метода, который использует отсортированный массив (по существу служит функцией мини-кучи, но с более легким поиском) и постоянно отслеживает, где находится пятидесятый процентиль общих весов. Я написал a blog post about it, где есть более подробные примеры.