Hoe verwerk je een datastroom om de mediaan te berekenen met beperkte geheugen?

Om de mediaan te berekenen in een datastroom met beperkt geheugen, worden algoritmen gebruikt die niet vereisen dat alle elementen worden opgeslagen. Een populaire aanpak is het bijhouden van twee datastructuren (bijvoorbeeld twee heaps):

• Een max-heap voor de onderste helft van de elementen
• Een min-heap voor de bovenste helft van de elementen

Wanneer een nieuw getal binnenkomt, wordt het toegevoegd aan een van de heaps, en vervolgens worden de groottes van de heaps in balans gebracht zodat ze niet meer dan 1 verschillen. De mediaan is dan of de wortel van de max-heap (als die groter is), of het gemiddelde van de wortels van beide heaps.

Deze methode maakt het mogelijk om de mediaan in O(log n) per element te verkrijgen en geheugen te gebruiken dat evenredig is aan het aantal elementen, zonder de hele stroom op te slaan.

Voorbeeld in Python:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # max-heap (omgekeerde waarden)
        self.high = [] # min-heap

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Verplaats het maximum uit low naar high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Balans de groottes
        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

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

Deze methode is efficiënt voor stroomverwerking met beperkt geheugen.