Como processar um fluxo de dados para calcular a mediana com memória limitada?

Para calcular a mediana num fluxo de dados com memória limitada, utilizam-se algoritmos que não requerem armazenar todos os elementos. Uma abordagem popular é manter duas estruturas de dados (por exemplo, duas heaps):

• Uma heap máxima para a metade inferior dos elementos
• Uma heap mínima para a metade superior dos elementos

Ao receber um novo número, ele é adicionado a uma das heaps, e depois os seus tamanhos são equilibrados para que não difiram mais do que um. Assim, a mediana é ou a raiz da heap máxima (se for maior), ou a média das raízes de ambas as heaps.

Este método permite obter a mediana em O(log n) por cada elemento e usar memória proporcional à quantidade de elementos, sem armazenar todo o fluxo.

Exemplo em Python:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # heap máximo (valores invertidos)
        self.high = [] # heap mínimo

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Mover o máximo de low para high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Equilibrar tamanhos
        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())

Este método é eficiente para processamento de fluxo com memória limitada.