Cum se procesează un flux de date pentru calcularea medianei cu memorie limitată?

Pentru calcularea medianei într-un flux de date cu memorie limitată, se utilizează algoritmi care nu necesită stocarea tuturor elementelor. O abordare populară este menținerea a două structuri de date (de exemplu, două heap-uri):

• Un heap maxim pentru jumătatea inferioară a elementelor
• Un heap minim pentru jumătatea superioară a elementelor

Când apare un nou număr, acesta este adăugat într-unul dintre heap-uri, apoi se echilibrează dimensiunile acestora pentru a nu diferi mai mult de 1. Mediana este apoi fie rădăcina heap-ului maxim (dacă este mai mare), fie media rădăcinilor ambelor heap-uri.

Această metodă permite obținerea medianei în O(log n) pentru fiecare element și utilizarea memoriei proporțional cu numărul de elemente, fără a stoca întregul flux.

Exemplu în Python:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # heap maxim (valorile inverse)
        self.high = [] # heap minim

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Mută maximul din low în high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Echilibrează dimensiunile
        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

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

Această metodă este eficientă pentru procesarea fluxurilor de date cu memorie limitată.