/
Kwasik
/
aaa-algorithms_2
Обзор
Документация
Войти
/
Kwasik
/
aaa-algorithms_2
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
homework-5
Task5_Heaps/solution_3.py
46 строк
2 KB
Eduard Shashkov
HW-5
29 дек 2024, 13:15
29 дек 2024, 13:15
33158ab
Код
Авторство
О чём код?
import heapq class StreamMedian: def __init__(self): # Max-heap для хранения меньшей половины чисел (храним как отрицательные значения) self.low = [] # Min-heap для хранения большей половины чисел self.high = [] def add_num(self, num: int) -> None: # Добавляем число в одну из куч if not self.low or num <= -self.low[0]: heapq.heappush(self.low, -num) else: heapq.heappush(self.high, num) # Балансируем кучи if len(self.low) > len(self.high) + 1: heapq.heappush(self.high, -heapq.heappop(self.low)) elif len(self.high) > len(self.low): heapq.heappush(self.low, -heapq.heappop(self.high)) def find_median(self) -> float: # Если общее количество чисел нечётное, медиана - вершина max-кучи if len(self.low) > len(self.high): return -self.low[0] # Если чётное, медиана - среднее двух вершин куч return (-self.low[0] + self.high[0]) / 2 def solution(): n = int(input()) stream = StreamMedian() for i in range(n): line = input().split() command = line[0] if command == "ADD": stream.add_num(int(line[1])) elif command == "FIND_MEDIAN": print(f'{stream.find_median():.1f}') solution()