Чектелген эс тутум менен медиананы эсептөө үчүн маалымат агымын кантип иштетсе болот?

Маалымат агымында медиананы эсептөө үчүн чектелген эс тутум менен, бардык элементтерди сактоо талап кылынбаган алгоритмдер колдонулат. Популярдуу ыкма — эки түзүмдү (мисалы, эки кучту) кармоо:

• Астыңкы жарым үчүн максималдуу куч
• Жогорку жарым үчүн минималдуу куч

Жаңы сан келгенде, ал бирине кошулат, андан кийин алардын өлчөмдөрү тең салмактуу болот, алардын айырмасы 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)
        # эң чоңдукту төмөнкү кучтөн жогору көчүрүү
        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())

Бул ыкма чектелген эс тутум менен агымдарды натыйжалуу иштетүүгө мүмкүндүк берет.