Berechnung eines laufenden Medians in C++

1. Laufender Median
2. Berechnung eines laufenden Medians in C++

Dies ist ein Tutorial zur effizienten Berechnung des laufenden Medians. Wir beginnen mit einer detaillierten Beschreibung des laufenden Medians, gefolgt von einem Algorithmus und einigen Überlegungen zur Implementierung.

Laufender Median

Der laufende Median ist eine effiziente Methode zur Berechnung einer Zahlenfolge. Die Intuition dahinter ist, dass wir, wenn wir uns für den Median interessieren, nicht alle Werte in der Sequenz kennen müssen, sondern stattdessen verfolgen können, wie viele Werte darüber oder darunter liegen.

Wenn es eine gerade Anzahl von Werten gibt, nehmen wir den Durchschnitt (oder Mittelwert) für beide Hälften und verwenden diesen als unseren neuen Mittelwert.

Der laufende Median beginnt mit der Beobachtung in der Mitte der sortierten Liste. Die nächste Beobachtung wird mit dieser mittleren Beobachtung verglichen; wenn er größer oder kleiner ist, wird er zum neuen Mittelpunkt.

Dieser Vorgang wird fortgesetzt, bis keine Beobachtungen mehr in der sortierten Liste verbleiben.

Berechnung eines laufenden Medians in C++

Der laufende Median wird unter Verwendung von zwei Heaps berechnet. Alle Werte kleiner oder gleich dem aktuellen Median befinden sich im linken Heap.

Alle, die größer oder gleich dem aktuellen Median sind, befinden sich im rechten Haufen.

Der laufende Median wird aktualisiert, indem jede Zahl in diesen beiden Haufen ausgetauscht wird. Um eine konstante Anzahl von Swaps aufrechtzuerhalten, müssen wir wissen, wann einer dieser beiden Heaps leer wird.

Wenn einer dieser beiden Heaps leer wird, bedeutet dies, dass alle Werte kleiner oder gleich dem aktuellen Median verarbeitet wurden und alle Werte größer oder gleich verarbeitet wurden. An diesem Punkt können wir mit einem Wert aus dem nicht leeren Heap tauschen, der immer entweder der linke Heap oder der richtige Heap ist, je nachdem, welcher zuerst geleert wurde.

Damit dieser Algorithmus funktioniert, benötigen wir eine Datenstruktur, die ein effizientes Einfügen und Löschen an beiden Enden unterstützt. Diese Datenstruktur sollte auch in der Lage sein, die Cache-Lokalität zu nutzen.