Wie verarbeitet man einen Datenstrom zur Berechnung des Medians mit begrenztem Speicher?

Um Algoritmus zur Berechnung des Medians in einem Datenstrom mit begrenztem Speicher verwendet Algorithmen, die nicht alle Elemente speichern müssen. Ein beliebter Ansatz ist, zwei Datenstrukturen zu pflegen (z.B. zwei Heaps):

• Max-Heap für die untere Hälfte der Elemente
• Min-Heap für die obere Hälfte der Elemente

Bei Eingang eines neuen Werts wird dieser in einen der Heaps eingefügt, und dann werden die Größen der Heaps so ausgeglichen, dass sie sich höchstens um 1 unterscheiden. Der Median ist dann entweder die Wurzel des Max-Heaps (wenn sie größer ist) oder der Durchschnitt der Wurzeln beider Heaps.

Diese Methode ermöglicht es, den Median in O(log n) pro Element zu berechnen und den Speicher proportional zur Anzahl der Elemente zu nutzen, ohne den gesamten Datenstrom zu speichern.

Beispiel in Python:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # Max-Heap (invertierte Werte)
        self.high = [] # Min-Heap

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Das Maximum aus low in high verschieben
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Größen ausgleichen
        if len(self.low) > len(self.high) + 1:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)
        elif len(self.high) > len(self.low):
            val = heapq.heappop(self.high)
            heapq.heappush(self.low, -val)

    def find_median(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        else:
            return (-self.low[0] + self.high[0]) / 2

# Verwendung:
finder = MedianFinder()
for num in [5, 15, 1, 3]:
    finder.add_num(num)
    print(finder.find_median())

Diese Methode ist effizient für die Verarbeitung von Datenströmen mit begrenztem Speicher.