Finden von einem Strom von Werten gewichteten Median laufen und Gewichte

Question

Der gewichtete Median einer Probe ist die 50% gewichtet Perzentil (siehe this post @ crossvalidated for more info)/

Ich habe mich gefragt, wie man den Algorithmus verlängern würde verwendet, um den Median zu finden ein laufender Zahlenstrom detailliert here (mit zwei Heaps, einem Min-Heap für die linke Seite und einem Max-Heap für die rechte Seite), um den gewichteten Median aus einem Strom von double Werten und Gewichten effizient zu berechnen.

Eine Idee, die ich hatte, war die gleiche Methode wie bei der Berechnung des Medians aus einem ungewichteten Zahlenstrom, aber einfach zusätzliche Werte, wenn die Gewichte nicht eins sind (zB würde ein Wert mit einem Gewicht von 2 eingefügt werden) zweimal). Jedoch skaliert dies nicht gut mit Gewichten, die verdoppelt werden können, und scheint auch ziemlich speicherineffizient zu sein.

Danke!

Answer 1

Ein Ansatz mit O (nlogn) -Komplexität wäre, die Knoten in einen erweiterten balancierten binären Suchbaum einzufügen. Der Baum würde nach Wert sortiert und jeder Knoten im Baum würde um ein Feld erweitert, das das Gesamtgewicht aller Tochterknoten angibt.

Es kostet O (logn), einen neuen Knoten einzufügen, einschließlich der Aktualisierung aller Gewichtungsfelder.

Um den Median nachzuschlagen, steigen Sie den Baum basierend auf einem Zielgewicht des Gesamtgewichts dividiert durch 2. Diese Suche dauert O (logn).

Answer 2

Ich endete mit der Implementierung einer Methode, die eine sortierte Array verwendet (im Wesentlichen dient die Funktion eines Min-Heap, aber mit einfacher Suche) und ständig verfolgt, wo das fünfzigste Perzentil der Gesamtgewichte sind. Ich schrieb a blog post about it, die ausführlichere Beispiele hat.