Cheklangan xotira bilan medianani hisoblash uchun ma'lumot oqimini qanday ishlash mumkin?

Cheklash uchun cheklangan xotira bilan ma'lumotlar oqimida medianani hisoblash uchun barcha elementlarni saqlashni talab qilmaydigan algoritmlar ishlatiladi. Mashhur yondashuvlardan biri, ikki tuzilmani (masalan, ikki toshni) saqlashdir:

• Pastki yarim uchun maksimal tosh
• Yuqori yarim uchun minimal tosh

Yangi raqam kelganda, u biriga qo'shiladi va keyin toshlarning o'lchamlari 1 dan ortiq bo'lmasligi uchun muvozanatlashadi. Shunday qilib, mediani yoki maksimal toshning ildizi (agar u katta bo'lsa), yoki ikkala toshning ildizlarining o'rtacha qiymati bo'ladi.

Ushbu usul har bir element uchun O(log n) da mediani olish imkonini beradi va xotirani elementlar soniga proporsional ravishda ishlatadi, ammo butun oqimni saqlamaydi.

Python misoli:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # maksimal tosh (qiymatlar teskari)
        self.high = [] # minimal tosh

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # maksimal toshdan yuqori tomoniga o'tkazish
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # o'lchamlarni muvozanatlash
        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

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

Ushbu usul cheklangan xotira bilan oqimlarni samarali tarzda ishlash imkonini beradi.