Ako spracovať tok dát na výpočet mediánu s obmedzenou pamäťou?

Na výpočet mediánu v toku dát s obmedzenou pamäťou sa používajú algoritmy, ktoré nevyžadujú uloženie všetkých prvkov. Jedným z populárnych prístupov je udržiavanie dvoch dátových štruktúr (napríklad dvoch hald):

• Max-heap pre spodnú polovicu prvkov
• Min-heap pre hornú polovicu prvkov

Keď príde nové číslo, pridá sa do jednej z hald a potom sa ich veľkosti vyvážia tak, aby sa líšili najviac o 1. Medián je buď koreň max-heapu (ak je väčší), alebo priemer koreňov oboch hald.

Táto metóda umožňuje získať medián v čase O(log n) pre každý prvok a používať pamäť úmernú počtu prvkov, bez uloženia celého toku.

Príklad v Pythone:

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)
        # Presun najväčšieho 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áženie veľkostí
        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žitie:
finder = MedianFinder()
for num in [5, 15, 1, 3]:
    finder.add_num(num)
    print(finder.find_median())

Táto metóda je efektívna pre spracovanie tokov s obmedzenou pamäťou.