¿Cómo procesar un flujo de datos para calcular la mediana con memoria limitada?

Para calcular la mediana en un flujo de datos con memoria limitada, se utilizan algoritmos que no requieren almacenar todos los elementos. Uno de los enfoques populares es mantener dos estructuras de datos (por ejemplo, dos montículos):

• Un montículo máximo para la mitad inferior de los elementos
• Un montículo mínimo para la mitad superior de los elementos

Al recibir un nuevo número, se añade a uno de los montículos y luego se equilibran sus tamaños para que no difieran en más de uno. La mediana es entonces ya sea la raíz del montículo máximo (si es mayor), o el promedio de las raíces de ambos montículos.

Este método permite obtener la mediana en O(log n) por cada elemento y usar memoria proporcional a la cantidad de elementos, sin almacenar todo el flujo.

Ejemplo en Python:

import heapq

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

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Mover el máximo de 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)

        # Equilibrar tamaños
        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 es eficiente para procesamiento en flujo con memoria limitada.