Чӣ гуна коркарди ҷараёни маълумот барои ҳисоб кардани медиана бо ёрии хотираи маҳдуд?

Барои ҳисоб кардани медиана дар ҷараёни додаҳо бо хотираи маҳдуд, алгоритмҳо истифода мешаванд, ки ниёз ба нигоҳдории ҳамаи унсурҳоро надоранд. Яке аз роҳҳои маъмул нигоҳ доштани ду сохторҳои дода (масалан, ду кӯҳ):

• Кӯҳи максималӣ барои ними поёнӣ аз унсурҳо
• Кӯҳи минималӣ барои ними болоӣ аз унсурҳо

Вақте ки як рақами нав меояд, он ба яке аз кӯҳҳо илова мешавад ва сипас андозаҳои онҳо баробар карда мешаванд, то ки фарқият на бештар аз 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)
        # интиқол додани баландтарин аз кӯҳи поёнӣ ба кӯҳи болоӣ
        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())

Ин усул барои кор бо ҷараёнҳои додаҳо бо хотираи маҳдуд самаранок аст.