Кучи и heapq

def sift_up(heap, i):
    while i > 0 and heap[(i - 1) // 2] > heap[i]:
        parent = (i - 1) // 2
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent

def sift_down(heap, i):
    n = len(heap)
    while True:
        smallest, left, right = i, 2 * i + 1, 2 * i + 2
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            return
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

def push(heap, x):
    heap.append(x)
    sift_up(heap, len(heap) - 1)

def pop(heap):
    heap[0], heap[-1] = heap[-1], heap[0]
    smallest = heap.pop()
    if heap:
        sift_down(heap, 0)
    return smallest

h = []
for x in [5, 3, 8, 1, 9, 2]:
    push(h, x)
    print(f"push {x}: {h}")
print([pop(h) for _ in range(6)])

import heapq

nums = [5, 3, 8, 1, 9, 2]
heapq.heapify(nums)                     # на месте, O(n)
print(nums, nums[0])

heapq.heappush(nums, 0)
print(heapq.heappop(nums), heapq.heappop(nums))
print(heapq.heappushpop(nums, 4))       # push, затем pop — быстрее двух вызовов
print(heapq.nlargest(3, [5, 1, 8, 3, 9]), heapq.nsmallest(2, [5, 1, 8, 3, 9]))

# max-куча: отрицательные значения
max_heap = [-x for x in [5, 1, 8]]
heapq.heapify(max_heap)
print(-heapq.heappop(max_heap))

# приоритетная очередь: кортежи (приоритет, счётчик, данные)
tasks = []
for order, (priority, name) in enumerate([(2, "отчёт"), (1, "пожар"), (3, "почта"), (1, "звонок")]):
    heapq.heappush(tasks, (priority, order, name))     # order — чтобы не сравнивать данные и сохранить порядок
while tasks:
    print(heapq.heappop(tasks))

import heapq
from collections import Counter

def top_k(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)        # pop + push
    return sorted(heap, reverse=True)

print(top_k([3, 1, 5, 12, 2, 11, 7], 3))

def top_k_frequent(words, k):
    counts = Counter(words)
    return heapq.nlargest(k, counts, key=counts.get)

print(top_k_frequent(["a", "b", "a", "c", "b", "a"], 2))

def k_closest(points, k):
    return heapq.nsmallest(k, points, key=lambda p: p[0] ** 2 + p[1] ** 2)

print(k_closest([(1, 3), (-2, 2), (5, 8), (0, 1)], 2))

import heapq

def merge_k(lists):
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    result = []
    while heap:
        value, i, j = heapq.heappop(heap)       # минимальный среди «голов» списков
        result.append(value)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return result

print(merge_k([[1, 4, 7], [2, 5, 8], [0, 3, 6, 9]]))
print(list(heapq.merge([1, 4, 7], [2, 5, 8])))   # готовая ленивая версия

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []          # max-куча меньшей половины (храним -x)
        self.high = []         # min-куча большей половины

    def add(self, num):
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))   # наибольший из меньших → в большие
        if len(self.high) > len(self.low):                     # балансируем размеры
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

m = MedianFinder()
for x in [5, 15, 1, 3, 8]:
    m.add(x)
    print(f"добавили {x}: медиана {m.median()}")