Πώς επεξεργαζόμαστε ένα ρεύμα δεδομένων για τον υπολογισμό της διάμεσου με περιορισμένη μνήμη;

Για τον υπολογισμό της διάμεσου σε μια ροή δεδομένων με περιορισμένη μνήμη, χρησιμοποιούνται αλγόριθμοι που δεν απαιτούν την αποθήκευση όλων των στοιχείων. Μία δημοφιλής προσέγγιση είναι η διατήρηση δύο δομών δεδομένων (π.χ. δύο σωρούς):

• Ένας μέγιστος σωρός για το κάτω μισό των στοιχείων
• Ένας ελάχιστος σωρός για το πάνω μισό των στοιχείων

Όταν λαμβάνεται ένας νέος αριθμός, προστίθεται σε έναν από τους σωρούς και στη συνέχεια ισορροπούν τα μεγέθη τους ώστε να μην διαφέρουν περισσότερο από 1. Η διάμεσος είναι είτε η ρίζα του μέγιστου σωρού (αν είναι μεγαλύτερη), είτε ο μέσος όρος των ριζών και των δύο σωρών.

Αυτή η μέθοδος επιτρέπει την εύρεση της διάμεσου σε χρόνο O(log n) για κάθε στοιχείο και τη χρήση μνήμης ανάλογη με τον αριθμό των στοιχείων, χωρίς να αποθηκεύει ολόκληρη τη ροή.

Παράδειγμα σε Python:

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []  # μέγιστος σωρός (αντιστροφή τιμών)
        self.high = [] # ελάχιστος σωρός

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        # Μεταφορά του μέγιστου από το low στο high
        if self.low and self.high and (-self.low[0]) > self.high[0]:
            val = -heapq.heappop(self.low)
            heapq.heappush(self.high, val)

        # Ισορροπία μεγέθους
        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

# Χρήση:
finder = MedianFinder()
for num in [5, 15, 1, 3]:
    finder.add_num(num)
    print(finder.find_median())

Αυτή η μέθοδος είναι αποδοτική για επεξεργασία ροών δεδομένων με περιορισμένη μνήμη.