Как обрабатывать поток данных для подсчёта медианы с ограниченной памятью?

Для подсчёта медианы в потоке данных с ограниченной памятью используют алгоритмы, которые не требуют хранения всех элементов. Один из популярных подходов — поддерживать две структуры данных (например, два кучи):

• Максимальная куча для нижней половины элементов
• Минимальная куча для верхней половины элементов

При поступлении нового числа его добавляют в одну из куч, затем балансируют размеры куч так, чтобы их размеры отличались не более чем на 1. Медиана при этом — это либо корень максимальной кучи (если она больше), либо среднее корней обеих куч.

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

Пример на Python:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # max heap (invert values)
        self.high = [] # min heap

    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())

Этот подход эффективен для потоковой обработки с ограниченной памятью.