Kısıtlı bellek ile medyan hesaplamak için veri akışını nasıl işleriz?

Sınırlı bellek ile veri akışında medyanı hesaplamak için tüm öğeleri saklamaya gerek olmayan algoritmalar kullanılır. Popüler yaklaşımlardan biri, iki veri yapısı (örneğin, iki yığın) tutmaktır:

• Alt yarı için maksimum yığın
• Üst yarı için minimum yığın

Yeni bir sayı geldiğinde, bunlardan birine eklenir ve ardından yığınların boyutları, en fazla 1 fark olacak şekilde dengelenir. Bu durumda medyan, ya maksimum yığının kökü (eğer daha büyükse) ya da her iki yığının köklerinin ortalaması olur.

Bu yöntem, her öğe için O(log n) zamanla medyanı elde etmeye ve belleği öğe sayısına orantılı kullanmaya olanak tanır, ancak tüm akışı saklamaz.

Python örneği:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # maksimum yığın (değerler ters çevrilmiş)
        self.high = [] # minimum yığın

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # low'dan yüksek'e en büyük değeri taşı
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Boyutları dengele
        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

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

Bu yöntem, sınırlı bellek ile akış verilerini etkin şekilde işler.