Jak przetwarzać strumień danych do obliczania mediany przy ograniczonej pamięci?

Aby obliczyć medianę w strumieniu danych z ograniczoną pamięcią, używa się algorytmów, które nie wymagają przechowywania wszystkich elementów. Jednym z popularnych podejść jest utrzymywanie dwóch struktur danych (np. dwóch kopców):

• Maksymalny kopiec dla dolnej połowy elementów
• Minimalny kopiec dla górnej połowy elementów

Gdy pojawia się nowa liczba, jest dodawana do jednego z kopców, a następnie ich rozmiary są równoważone tak, aby różniły się nie więcej niż o 1. Wtedy mediana to albo korzeń kopca maksymalnego (jeśli jest większy), albo średnia korzeni obu kopców.

Metoda ta pozwala na uzyskanie mediany w czasie O(log n) dla każdego elementu i korzystanie z pamięci proporcjonalnej do liczby elementów, bez przechowywania całego strumienia.

Przykład w Python:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # kopiec maksymalny (wartości odwrócone)
        self.high = [] # kopiec minimalny

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Przesuń największy z low do high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Równoważenie rozmiarów
        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

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

Metoda ta jest efektywna dla strumieni danych z ograniczoną pamięcią.