Comment traiter un flux de données pour calculer la médiane avec une mémoire limitée?

Pour calculer la médiane dans un flux de données avec une mémoire limitée, on utilise des algorithmes qui ne nécessitent pas de stocker tous les éléments. Une approche populaire consiste à maintenir deux structures de données (par exemple, deux tas) :

• Un tas max pour la moitié inférieure des éléments
• Un tas min pour la moitié supérieure des éléments

Lorsqu’un nouveau nombre arrive, il est ajouté à l’un des tas, puis leurs tailles sont équilibrées pour qu’elles ne diffèrent pas de plus d’un. La médiane est alors soit la racine du tas max (si elle est plus grande), soit la moyenne des racines des deux tas.

Cette méthode permet d’obtenir la médiane en O(log n) pour chaque élément et d’utiliser une mémoire proportionnelle au nombre d’éléments, sans stocker tout le flux.

Exemple en Python :

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # tas max (valeurs inversées)
        self.high = [] # tas min

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Déplacer le maximum de low vers high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Équilibrer les tailles
        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

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

Cette méthode est efficace pour le traitement en flux avec une mémoire limitée.