Как да обработваме поток от данни за изчисляване на медиана с ограничена памет?

За изчисляване на медиана в поток от данни с ограничена памет се използват алгоритми, които не изискват съхраняване на всички елементи. Един от популярните подходи е поддържането на две структури от данни (например, две купи):

• Максимална купа за долната половина на елементите
• Минимална купа за горната половина на елементите

Когато се получи ново число, то се добавя към една от купите, след което размерите им се балансират така, че да не се различават повече от 1. Медианата е или коренът на максималната купа (ако е по-голяма), или средната стойност на корените и на двете купи.

Този метод позволява да се получи медиана за O(log n) за всеки елемент и да се използва памет пропорционално на броя на елементите, без да се съхранява целият поток.

Пример на Python:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # максимална купа (инвертирани стойности)
        self.high = [] # минимална купа

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # прехвърляне на най-голямото от low към high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # балансиране на размерите
        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

# Използване:
finder = MedianFinder()
for num in [5, 15, 1, 3]:
    finder.add_num(num)
    print(finder.find_median())

Този метод е ефективен за обработка на потокове с ограничена памет.