Məhdud yaddaşla medianı hesablamaq üçün məlumat axınını necə işləmək olar?

Məhdud yaddaş ilə məlumat axınında medianı hesablamaq üçün bütün elementləri saxlamağa ehtiyac olmayan alqoritmlər istifadə olunur. Populyar yanaşmalardan biri iki məlumat quruluşunu saxlamaqdır (məsələn, iki yığın):

• Aşağı yarım üçün maksimum yığın
• Yuxarı yarım üçün minimum yığın

Yeni bir ədəd daxil olduqda, o, birinə əlavə olunur və sonra yığınların ölçüləri balanslaşdırılır ki, aralarındakı fərq 1-dən çox olmasın. Bu zaman median ya maksimum yığın kökü (əgər o daha böyükdür), ya da hər iki yığının köklərinin orta qiyməti olur.

Bu metod hər element üçün O(log n) vaxtda medianı əldə etməyə imkan verir və yaddaşı elementlərin sayına görə istifadə edir, amma bütün axını saxlamaq lazım deyil.

Python nümunəsi:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # maksimum yığın (əks qiymətlər)
        self.high = [] # minimum yığın

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # ən böyük elementi yuxarı yığmağa köçür
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # ölçüləri balanslaşdır
        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

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

Bu metod məhdud yaddaş ilə axınların effektiv işlənməsinə imkan verir.