Kako obraditi tok podataka za izračunavanje medijane sa ograničenom memorijom?

Za izračunavanje medijane u toku podataka sa ograničenom memorijom koriste se algoritmi koji ne zahtevaju skladištenje svih elemenata. Jedan od popularnih pristupa je održavanje dve strukture podataka (na primer, dve hrpe):

• Maksimalna hrpa za donju polovinu elemenata
• Minimalna hrpa za gornju polovinu elemenata

Kada stigne novi broj, on se dodaje u jednu od hrpa, a zatim se njihovi veličine uravnotežuju tako da se razlikuju najviše za 1. Medijana je ili koren maksimalne hrpe (ako je veći), ili srednja vrednost korena obe hrpe.

Ovaj metod omogućava dobijanje medijane u O(log n) za svaki element i korišćenje memorije proporcionalno broju elemenata, bez čuvanja celog toka.

Primer u Pythonu:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # maksimalna hrpa (inverzne vrednosti)
        self.high = [] # minimalna hrpa

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Prebacivanje najvećeg iz low u high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Uravnoteženje veličina
        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

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

Ovaj metod je efikasan za obradu tokova sa ograničenom memorijom.