Jak zpracovat datový tok pro výpočet mediánu s omezenou pamětí?

Pro výpočet mediánu v datovém toku s omezenou pamětí se používají algoritmy, které nevyžadují ukládání všech prvků. Jedním z oblíbených přístupů je udržování dvou datových struktur (například dvou hald):

• Max-heap pro spodní polovinu prvků
• Min-heap pro horní polovinu prvků

Když přijde nové číslo, přidá se do jedné z hald a poté se jejich velikosti vyváží tak, aby se lišily maximálně o 1. Medián je pak buď kořen max-heapu (je-li větší), nebo průměr kořenů obou hald.

Tato metoda umožňuje získat medián v čase O(log n) pro každý prvek a používat paměť úměrnou počtu prvků, aniž by bylo nutné uložit celý tok.

Příklad v Pythonu:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # max-heap (invertované hodnoty)
        self.high = [] # min-heap

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Přesunout maximum 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)

        # Vyvážení velikostí
        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

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

Tato metoda je efektivní pro zpracování datových toků s omezenou pamětí.