Come elaborare un flusso di dati per calcolare la mediana con memoria limitata?

Per calcolare la mediana in un flusso di dati con memoria limitata, si utilizzano algoritmi che non richiedono di memorizzare tutti gli elementi. Un approccio popolare consiste nel mantenere due strutture dati (ad esempio, due heap):

• Un max-heap per la metà inferiore degli elementi
• Un min-heap per la metà superiore degli elementi

Quando arriva un nuovo numero, viene aggiunto a uno dei due heap, e poi si bilanciano le loro dimensioni in modo che differiscano al massimo di 1. La mediana è quindi o la radice del max-heap (se più grande), o la media delle radici di entrambi gli heap.

Questo metodo permette di ottenere la mediana in O(log n) per ogni elemento e di usare memoria proporzionale alla quantità di elementi, senza memorizzare tutto il flusso.

Esempio in Python:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # max-heap (valori invertiti)
        self.high = [] # min-heap

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Sposta il massimo da low a high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Bilancia le dimensioni
        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

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

Questo metodo è efficiente per l'elaborazione di flussi di dati con memoria limitata.