Кучи и приоритетные очереди

Есть класс задач, в которых нужен не «весь порядок», а ровно один вопрос: кто следующий? Какая задача в планировщике должна выполниться раньше всех. Какая вершина в алгоритме Дейкстры сейчас ближе всего к старту. Какой из миллиона запросов имеет наибольший скор. Какое событие в дискретной симуляции произойдёт первым. Какие два самых редких символа слить в дереве Хаффмана.

Полная сортировка на такой вопрос отвечает — и жестоко переплачивает. Она даёт нам порядок между всеми парами элементов, а нам нужен один экстремум, и то в постоянно меняющемся множестве. Куча — это структура, которая держит ровно столько порядка, сколько нужно для ответа «кто минимальный», и ни каплей больше. За счёт этой экономии она получает O(log n) на вставку и удаление минимума при нулевых накладных расходах по памяти — вообще ни одного указателя.

Статья предполагает, что вы уже прошли массивы и динамические массивы, очереди и модель стоимости с амортизацией, а также знакомы с бинарными деревьями поиска — с ними кучу постоянно путают, и разобраться в различии стоит с самого начала.

Приоритетная очередь как абстрактный тип

Сначала интерфейс, потом реализация. Приоритетная очередь (priority queue) — это АТД с тремя обязательными операциями:

И тремя опциональными, которые в реальных задачах оказываются критичными:

Заметьте: приоритетная очередь — это не очередь. Обычная FIFO-очередь — частный случай приоритетной, где приоритет равен времени поступления. Но общий случай ничего не гарантирует про порядок среди равных приоритетов: куча не стабильна, и это регулярный источник багов (о нём ниже).

Почему наивные реализации не годятся

Прежде чем строить кучу, полезно понять, что именно она улучшает.

Наивные варианты «размазывают» стоимость неравномерно: один конец O(1), другой O(n). Если в рабочей нагрузке и вставок, и извлечений примерно поровну (а так почти всегда), суммарно получается Θ(n) на операцию. Сбалансированное дерево решает проблему, но покупает лишнего: оно поддерживает полный порядок и умеет искать любой ключ, а нам нужен только экстремум. Куча — это «дерево поиска, урезанное до одной задачи», и урезание окупается константой и памятью.

Инвариант кучи: минимум порядка ради максимума скорости

Бинарная min-куча — это бинарное дерево с двумя свойствами.

1. Свойство порядка (heap property). Для любого узла его ключ ≤ ключей обоих детей. Следствие: минимум всего множества лежит в корне. Между братьями порядка нет — именно на этом мы экономим.
2. Свойство формы. Дерево полное (complete): все уровни заполнены слева направо, кроме, возможно, последнего, который заполнен слева. Следствие: высота ровно ⌊log₂ n⌋.

Второе свойство — не эстетика, а инженерная находка. Полное дерево можно уложить в массив без указателей: обход по уровням даёт каноническую нумерацию, а связи «родитель — ребёнок» превращаются в арифметику индексов.

left(i)   = 2*i + 1
right(i)  = 2*i + 2
parent(i) = (i - 1) // 2

(Если индексировать с единицы, формулы становятся ещё симпатичнее: 2i, 2i+1, i//2. Некоторые реализации специально тратят нулевую ячейку ради этого.)

Что это даёт на практике:

• Ноль накладной памяти. Дерево на n узлов занимает ровно n слотов. Сравните с красно-чёрным деревом: два указателя, бит цвета, заголовок аллокации — легко ×4 по памяти.
• Локальность. Верхние уровни кучи — это первые ячейки массива, они горячие и почти всегда в L1/L2. Спуск от корня трогает всё более разреженные адреса, но первые 3–4 шага бесплатны по кешу. Указательное дерево платит промахом на каждом уровне (см. модель памяти).
• Нет аллокаций на элемент. Рост — амортизированное удвоение динамического массива.

И чего это стоит: куча не умеет искать. Найти в куче произвольный ключ — это O(n), линейный скан массива. Куча не отвечает на «дай все ключи от A до B», «дай следующий за X», «выведи всё по порядку». Если эти вопросы есть в требованиях — вам нужно дерево, а не куча.

Важное различие с BST, которое стоит закрепить: в дереве поиска порядок горизонтальный (левое поддерево < узел < правое), в куче — вертикальный (родитель < оба ребёнка). BST знает всё обо всех; куча знает только то, что корень — минимум.

Таксономия: одно название, десяток структур

Дальше мы подробно разберём бинарную кучу (её нужно уметь писать с закрытыми глазами), затем — когда и зачем берут остальные.

Две операции, из которых состоит всё

Любое изменение кучи временно ломает свойство порядка ровно в одном месте, и обе процедуры восстановления — это движение «испорченного» элемента по вертикали.

sift-up (просеивание вверх)

Ситуация: элемент в позиции i может быть меньше своего родителя (так бывает после вставки в конец массива). Меняем его с родителем местами и повторяем, пока не встанет на место или не дойдём до корня.

def _sift_up(heap: list, i: int) -> None:
    """Поднимает элемент heap[i] вверх, пока не восстановится свойство кучи.
    Стоимость: O(log n) обменов в худшем случае — длина пути до корня."""
    item = heap[i]                      # запоминаем, чтобы не делать полноценные swap'ы
    while i > 0:
        parent = (i - 1) >> 1
        if heap[parent] <= item:        # родитель уже не больше — место найдено
            break
        heap[i] = heap[parent]          # сдвигаем родителя вниз (одно присваивание вместо swap)
        i = parent
    heap[i] = item

Приём с «дыркой» вместо обменов (hole trick) экономит треть присваиваний: вместо трёх присваиваний на каждый swap делаем одно, а исходный элемент кладём в самом конце. Мелочь, но в горячем цикле heapsort она заметна.

sift-down (просеивание вниз)

Ситуация: элемент в позиции i может быть больше кого-то из детей (так бывает после того, как мы переставили последний элемент массива в корень). Меняем его с меньшим из детей и повторяем.

Ключевая деталь, на которой спотыкаются: менять надо именно с минимальным ребёнком. Если поменять с бо́льшим, свойство порядка сломается в новой точке — этот ребёнок окажется больше своего брата.

def _sift_down(heap: list, i: int, n: int) -> None:
    """Опускает элемент heap[i] вниз по куче размера n.
    Стоимость: O(log n), два сравнения на уровень."""
    item = heap[i]
    while True:
        left = 2 * i + 1
        if left >= n:                   # детей нет
            break
        smallest = left
        right = left + 1
        if right < n and heap[right] < heap[left]:
            smallest = right            # ВАЖНО: спускаемся к МЕНЬШЕМУ ребёнку
        if heap[smallest] >= item:      # оба ребёнка не меньше — место найдено
            break
        heap[i] = heap[smallest]
        i = smallest
    heap[i] = item

Полная бинарная куча

class MinHeap:
    """Бинарная min-куча поверх обычного списка.
    Инвариант: для всех i > 0 выполняется data[(i-1)//2] <= data[i]."""

    __slots__ = ("data",)

    def __init__(self, items=None):
        self.data = list(items) if items else []
        if len(self.data) > 1:
            self._heapify()             # построение за O(n), а не n × push

    def __len__(self):
        return len(self.data)

    def push(self, item) -> None:
        """O(log n) в худшем случае, O(1) амортизированно на случайных данных."""
        self.data.append(item)          # кладём в первую свободную позицию — конец массива
        _sift_up(self.data, len(self.data) - 1)

    def peek(self):
        """O(1). Минимум всегда в корне."""
        if not self.data:
            raise IndexError("peek из пустой кучи")
        return self.data[0]

    def pop(self):
        """Извлечь минимум. O(log n)."""
        if not self.data:
            raise IndexError("pop из пустой кучи")
        last = self.data.pop()          # снимаем последний лист — форма сохраняется
        if not self.data:
            return last
        top = self.data[0]
        self.data[0] = last             # ставим лист в корень и просеиваем вниз
        _sift_down(self.data, 0, len(self.data))
        return top

    def pushpop(self, item):
        """Положить и сразу извлечь минимум — дешевле, чем push + pop.
        Одно просеивание вниз вместо просеивания вверх и вниз."""
        if self.data and self.data[0] < item:
            item, self.data[0] = self.data[0], item
            _sift_down(self.data, 0, len(self.data))
        return item

    def replace(self, item):
        """Извлечь минимум и положить новый элемент. Размер кучи не меняется.
        Базовая операция для top-k и для k-путевого слияния."""
        top = self.data[0]              # бросит IndexError на пустой куче — так и надо
        self.data[0] = item
        _sift_down(self.data, 0, len(self.data))
        return top

    def _heapify(self) -> None:
        """Построение кучи из произвольного массива за O(n)."""
        n = len(self.data)
        for i in range(n // 2 - 1, -1, -1):   # обходим только внутренние узлы, снизу вверх
            _sift_down(self.data, i, n)

Обратите внимание на pushpop и replace. Это не украшательства: в задачах top-k и слияния потоков они выполняются миллионы раз, и экономия одного просеивания из двух — это буквально двукратное ускорение внутреннего цикла. В стандартной библиотеке Python они называются heapq.heappushpop и heapq.heapreplace.

Почему pop берёт именно последний лист

Частый вопрос: почему после удаления корня мы тащим наверх последний элемент массива — заведомо один из самых больших? Не логичнее ли поднять меньшего из детей?

Логичнее по количеству сравнений — но тогда сломается форма. Подъём ребёнка оставляет дырку где-то в середине последнего уровня, дерево перестаёт быть полным, и вся арифметика индексов рассыпается. Мы сознательно жертвуем несколькими лишними сравнениями ради того, чтобы структура оставалась неявной. Это и есть главный компромисс кучи.

Построение кучи за O(n): классический сюрприз

Наивный способ построить кучу из массива — n раз вызвать push. Стоимость: Θ(n log n).

Правильный способ — heapify: пройти внутренние узлы справа налево, снизу вверх и просеять каждый вниз. Стоимость: Θ(n). Это не опечатка и не амортизация — это честная линейная оценка худшего случая.

Интуиция: половина всех узлов — листья, для них работа равна нулю. Четверть узлов сидит на предпоследнем уровне, у них максимум один шаг. И только один узел — корень — может пройти всю высоту. Дорогих узлов экспоненциально мало.

Формально: на уровне k от низа находится не более ⌈n / 2^(k+1)⌉ узлов, каждый просеивается не более чем на k шагов.

              ⌊log n⌋                        ∞
    T(n)  ≤     Σ      (n / 2^(k+1)) · k  =  (n/2) · Σ  k / 2^k  =  (n/2) · 2  =  n
              k = 0                         k = 0

Ряд Σ k/2^k сходится к 2 — вот и весь фокус. Именно поэтому в порядке обхода в _heapify критично идти от n//2 - 1 к нулю, а не наоборот: sift-down корректен только тогда, когда оба поддерева уже являются кучами.

Практический вывод. Если у вас на руках уже есть готовый массив, никогда не стройте кучу циклом push’ей. heapq.heapify(lst) вместо for x in lst: heappush(h, x) — это разница между Θ(n) и Θ(n log n) на пустом месте.

Heapsort и почему им всё-таки редко сортируют

Куча даёт сортировку почти бесплатно: построить кучу за O(n), затем n раз извлечь минимум. В in-place варианте используют max-кучу и складывают извлечённые максимумы в освобождающийся хвост того же массива.

def heapsort(a: list) -> None:
    """Сортировка на месте по возрастанию. O(n log n) в худшем случае, O(1) доп. памяти.
    Использует max-кучу: максимум уезжает в конец массива."""
    n = len(a)

    def sift_down_max(i: int, size: int) -> None:
        item = a[i]
        while True:
            left = 2 * i + 1
            if left >= size:
                break
            largest = left
            right = left + 1
            if right < size and a[right] > a[left]:
                largest = right
            if a[largest] <= item:
                break
            a[i] = a[largest]
            i = largest
        a[i] = item

    for i in range(n // 2 - 1, -1, -1):   # фаза 1: построение max-кучи, O(n)
        sift_down_max(i, n)

    for end in range(n - 1, 0, -1):       # фаза 2: n-1 извлечений, O(n log n)
        a[0], a[end] = a[end], a[0]       # максимум встаёт на своё финальное место
        sift_down_max(0, end)             # куча уменьшилась на элемент

Свойства heapsort:

• Θ(n log n) в худшем случае — не «в среднем», как у quicksort. Никаких патологических входов.
• O(1) дополнительной памяти — настоящая in-place сортировка.
• Не стабильна — равные элементы перемешиваются.

Почему тогда sort() в стандартных библиотеках — это Timsort или pdqsort, а не heapsort? Из-за кеша. Quicksort сканирует память последовательно, префетчер работает идеально. Heapsort прыгает по индексам i, 2i+1, 4i+3… — шаг растёт экспоненциально, и начиная с некоторого уровня каждое обращение это промах в кеш. На больших массивах heapsort проигрывает хорошему quicksort в 2–3 раза при одинаковой асимптотике. Классическая иллюстрация того, почему O-нотация — не вся правда (подробнее в статье про модель памяти).

Тем не менее heapsort живёт в проде — как страховка. std::sort в libstdc++ реализует introsort: работает quicksort, но если глубина рекурсии превысила 2 log n (признак злонамеренного или неудачного входа), алгоритм переключается на heapsort и гарантирует O(n log n). Аналогично устроен pdqsort в Rust и Go.

d-арные кучи: настройка под железо

Ничто не обязывает нас брать ровно двух детей. В d-арной куче у узла d детей:

children(i) = d*i + 1, ..., d*i + d
parent(i)   = (i - 1) // d

Что меняется:

Sift-up ускоряется (дерево ниже), sift-down замедляется (на каждом уровне надо найти минимум из d детей). Формально d·log_d n минимизируется при d = e ≈ 2.7, то есть при d=2 или d=3.

Но реальность интереснее: d детей лежат в памяти подряд, и при d = 4 (а иногда 8 или 16) все дети умещаются в одну кеш-линию. Одна загрузка вместо двух-трёх. Поэтому 4-арная куча на практике часто быстрее бинарной, особенно если операций decrease_key много, как в Дейкстре на плотном графе.

Это не теория: рантайм Go долгое время использовал именно четвертичную кучу для таймеров (runtime/time.go), и Boost предоставляет boost::heap::d_ary_heap с настраиваемой арностью.

decrease-key: операция, которая ломает наивную кучу

Дейкстра и Прим устроены одинаково: держим приоритетную очередь вершин, извлекаем ближайшую, релаксируем рёбра — и уменьшаем приоритет уже лежащих в очереди соседей.

Проблема: чтобы уменьшить ключ элемента, надо знать, где он лежит. А куча, как мы выяснили, искать не умеет — поиск по значению это O(n), что убивает всю асимптотику.

Есть два решения, и оба используются в проде.

Решение 1: индексированная приоритетная очередь

Держим сбоку хеш-таблицу «идентификатор элемента → его позиция в массиве кучи» и аккуратно обновляем её при каждом обмене.

class IndexedMinPQ:
    """Приоритетная очередь с поддержкой decrease_key и удаления по ключу.
    Инвариант: pos[key] — актуальный индекс записи key в массиве heap."""

    def __init__(self):
        self.heap: list[tuple[float, object]] = []   # (приоритет, ключ)
        self.pos: dict[object, int] = {}             # ключ -> индекс в heap

    def _swap(self, i: int, j: int) -> None:
        """Единственное место, где меняются позиции — здесь же чиним индекс.
        Пропустить обновление pos — самый частый способ сломать эту структуру."""
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
        self.pos[self.heap[i][1]] = i
        self.pos[self.heap[j][1]] = j

    def _up(self, i: int) -> None:            # тот же sift-up, но обмены идут через _swap
        while i > 0 and self.heap[(i - 1) >> 1][0] > self.heap[i][0]:
            self._swap(i, (i - 1) >> 1)
            i = (i - 1) >> 1

    def _down(self, i: int) -> None:          # тот же sift-down, но обмены идут через _swap
        n = len(self.heap)
        while True:
            l, r, m = 2 * i + 1, 2 * i + 2, i
            if l < n and self.heap[l][0] < self.heap[m][0]:
                m = l
            if r < n and self.heap[r][0] < self.heap[m][0]:
                m = r
            if m == i:
                break
            self._swap(i, m)
            i = m

    def push(self, key, priority: float) -> None:
        """Вставка нового ключа. O(log n)."""
        if key in self.pos:
            raise KeyError(f"ключ {key!r} уже в очереди — используйте decrease_key")
        self.heap.append((priority, key))
        self.pos[key] = len(self.heap) - 1
        self._up(len(self.heap) - 1)

    def decrease_key(self, key, priority: float) -> None:
        """Уменьшить приоритет существующего ключа. O(log n) — только просеивание вверх."""
        i = self.pos[key]
        if priority > self.heap[i][0]:
            raise ValueError("decrease_key не может увеличивать приоритет")
        self.heap[i] = (priority, key)
        self._up(i)

    def pop(self):
        """Извлечь минимум: (приоритет, ключ). O(log n)."""
        top = self.heap[0]
        last = self.heap.pop()
        del self.pos[top[1]]
        if self.heap:
            self.heap[0] = last
            self.pos[last[1]] = 0
            self._down(0)
        return top

Стоимость: та же O(log n), но с константой хеш-таблицы и лишним обращением к памяти на каждый обмен. Зато размер кучи никогда не превышает числа уникальных ключей — важно, когда рёбер на порядки больше вершин.

Решение 2: ленивое удаление (lazy deletion)

Куда проще: не трогаем старую запись, а просто кладём новую с меньшим приоритетом. При извлечении проверяем — не устарела ли запись, и если да, молча выбрасываем.

import heapq
from math import inf

def dijkstra(graph: dict, source):
    """Кратчайшие пути из source. graph: {u: [(v, вес), ...]}, веса неотрицательные.
    Ленивое удаление вместо decrease_key.
    Время: O(E log E) = O(E log V). Память: O(E) в худшем случае — размер кучи."""
    dist = {source: 0.0}
    pq = [(0.0, source)]                    # куча из (расстояние, вершина)
    visited = set()

    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:                    # запись устарела — вершину уже обработали
            continue                        # ЭТА строчка и есть всё "ленивое удаление"
        visited.add(u)
        for v, w in graph.get(u, ()):
            nd = d + w
            if nd < dist.get(v, inf):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))  # старая запись про v остаётся мусором
    return dist

Сравнение подходов:

Так как log E ≤ log V² = 2 log V, асимптотика не меняется. Поэтому в 95% боевого кода (включая практически все реализации Дейкстры на Python, Go и Java, которые вы встретите) используется именно ленивое удаление. Индексированная куча оправдана, когда граф плотный и рост кучи до O(E) грозит памятью, либо когда нужно ещё и удалять элементы по ключу.

Третий, более радикальный вариант ленивого удаления: держать множество «отменённых» идентификаторов и периодически, когда доля мусора превысит, скажем, 50%, пересобирать кучу целиком через heapify за O(n). Так делают в планировщиках задач с большим числом отмен.

Мержабельные кучи: биномиальные, Фибоначчиевы, парные

Бинарная куча плохо умеет одну вещь — сливаться. Объединить две кучи размеров n и m можно только через heapify за O(n + m). Для этого придумали семейство указательных куч, где meld стоит O(log n) или даже O(1).

* — амортизированная оценка.

Фибоначчиева куча (Fredman & Tarjan, 1987) — теоретический чемпион. Её строка «decrease-key за O(1) амортизированно» напрямую улучшает Дейкстру с O(E log V) до O(E + V log V), что асимптотически лучше на плотных графах. Устройство: лес деревьев, ленивое слияние при вставке, а вся работа откладывается до delete_min, где выполняется консолидация деревьев одинакового ранга. decrease_key просто отрезает узел и переносит в корневой список, помечая родителя; при второй потере ребёнка родитель тоже отрезается — это «правило каскадного отсечения», которое и удерживает рангово-размерную границу (отсюда числа Фибоначчи в названии).

И почти никто её не использует. Причины:

• Огромные константы: четыре указателя на узел, поле ранга, бит метки.
• Катастрофическая локальность: каждая операция — прогулка по разбросанным по куче объектам.
• Амортизация означает, что отдельные delete_min могут быть очень дорогими — плохо для систем с требованиями к хвостовой латентности.

Ларкин, Сен и Тарьян (тот самый Тарьян) в 2014 году провели прямое эмпирическое сравнение и получили результат: на реальных нагрузках простые d-арные кучи и парные кучи стабильно обгоняют Фибоначчиевы (arXiv:1403.0252). Это одна из лучших статей для понимания, где заканчивается асимптотика и начинается инженерия.

Парная куча (pairing heap) — практичный компромисс: устройство почти тривиально (мультипутевое дерево, meld = подвесить корень к корню, delete_min = попарное слияние детей в два прохода), а на практике она быстра. Её используют в boost::heap::pairing_heap и в некоторых планировщиках.

Левацкие (leftist) и косые (skew) кучи — минималистичные мержабельные кучи, где meld рекурсивно сливает правые спины. Их любят в функциональных языках, потому что они естественно персистентны и пишутся в 20 строк — например, в Elixir или на любом другом иммутабельном стеке. Подробнее о персистентности — в статье про персистентные структуры.

Пять задач, где куча — правильный ответ

1. Top-k из потока

Найти k наибольших элементов среди n, где n огромно или вообще не помещается в память.

Наивно: отсортировать всё, взять хвост — O(n log n) времени и O(n) памяти. С кучей: держим min-кучу размера k и сравниваем каждый новый элемент с её корнем.

def top_k(stream, k: int) -> list:
    """k наибольших элементов потока. Время O(n log k), память O(k).
    Ключевая идея: min-куча размера k, её корень — «порог входа»."""
    heap = []
    for item in stream:
        if len(heap) < k:
            heapq.heappush(heap, item)
        elif item > heap[0]:                 # больше самого слабого из текущих лидеров
            heapq.heapreplace(heap, item)    # одно просеивание вниз вместо pop+push
    return sorted(heap, reverse=True)

Память O(k) вместо O(n) — вот почему так делают Elasticsearch, Lucene и любой поисковый движок: чтобы выдать 10 лучших документов из 50 миллионов, вам не нужно сортировать 50 миллионов. Отсечение по heap[0] дополнительно даёт возможность пропускать документы, которые заведомо не наберут нужный скор — приём WAND / block-max.

Если же весь массив в памяти и вы готовы его портить, quickselect даёт O(n) в среднем и обгоняет кучу. Но для потоков и для «памяти жалко» куча вне конкуренции.

2. Слияние k отсортированных потоков

Основа внешней сортировки, компакции LSM-деревьев и merge-фазы MapReduce.

def merge_sorted(*streams):
    """k-путевое слияние. Время O(N log k), где N — суммарное число элементов.
    Память O(k) — по одному «фронтовому» элементу от каждого потока."""
    heap = []
    iters = [iter(s) for s in streams]
    for idx, it in enumerate(iters):
        first = next(it, None)
        if first is not None:
            heap.append((first, idx))        # idx нужен, чтобы знать, откуда брать следующий
    heapq.heapify(heap)                      # O(k), а не k×push

    while heap:
        value, idx = heap[0]
        yield value
        nxt = next(iters[idx], None)
        if nxt is None:
            heapq.heappop(heap)              # поток исчерпан — убираем из фронта
        else:
            heapq.heapreplace(heap, (nxt, idx))

Именно так устроены heapq.merge в Python, компакция SSTable в RocksDB/LevelDB/Cassandra и слияние сегментов в Lucene. Альтернатива для очень больших k — дерево проигравших (loser tree, tournament tree), которое делает ровно одно сравнение на уровень вместо двух.

3. Скользящая медиана: две кучи

Классический приём, который стоит знать: медиана поддерживается двумя кучами, растущими навстречу друг другу. Max-куча держит меньшую половину, min-куча — большую. Медиана — корень одной из них.

class RunningMedian:
    """Медиана потока за O(log n) на добавление, O(1) на чтение.
    lo — max-куча (через отрицание) для меньшей половины, hi — min-куча для большей.
    Инвариант: len(lo) == len(hi) или len(lo) == len(hi) + 1, и max(lo) <= min(hi)."""

    def __init__(self):
        self.lo: list[float] = []   # хранит -x, чтобы эмулировать max-кучу
        self.hi: list[float] = []

    def add(self, x: float) -> None:
        # проталкиваем через lo в hi — так балансировка получается в две строки
        heapq.heappush(self.hi, -heapq.heappushpop(self.lo, -x))
        if len(self.hi) > len(self.lo):                 # выравниваем размеры
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def median(self) -> float:
        if not self.lo:
            raise ValueError("пустой поток")
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Тот же приём обобщается на любой квантиль и на IQR. Для скользящего окна с удалением старых элементов чистых куч уже мало — нужен либо индексированный вариант с ленивым удалением, либо дерево Фенвика по значениям.

4. Планировщик задач и дискретная симуляция

Куча по времени срабатывания — каноническая реализация таймеров и event-driven симуляции.

peek() за O(1) здесь принципиален: он говорит циклу событий, на сколько именно можно уснуть в epoll_wait/kqueue. Без приоритетной очереди пришлось бы либо просыпаться по тику (джиттер и лишние пробуждения — враг энергоэффективности), либо сканировать все таймеры.

Именно так устроены таймеры в libuv (min-куча), в рантайме Go (четвертичная куча на каждый P) и в большинстве сетевых библиотек.

5. Жадные алгоритмы: Хаффман, Прим, A*

• Код Хаффмана: n-1 раз извлечь два минимальных веса и вставить их сумму — O(n log n).
• Алгоритм Прима для MST: та же схема, что у Дейкстры, только ключ — вес ребра, а не расстояние. (Второй классический алгоритм MST, Краскала, вместо кучи опирается на DSU.)
• A*: та же куча, но приоритет f = g + h. Правильный выбор структуры особенно важен, потому что в A* один узел переоткрывается много раз.

Все три подробно разбираются в контексте представлений графов — выбор между списком смежности и матрицей напрямую влияет на то, какая куча вам подойдёт.

Когда куча — неправильный ответ

Полезнее знать границы, чем сильные стороны. Куча выигрывает ровно в одном углу пространства задач: ключи произвольные (их можно только сравнивать) и нужен только экстремум. Стоит сдвинуться по любой из двух осей — и правильный ответ меняется.

Ключи — малые целые числа. Если приоритеты лежат в [0, C) при небольшом C, куча переплачивает логарифм. Берите бакетную очередь: массив из C списков плюс указатель на первый непустой бакет. Дейкстра на такой очереди (алгоритм Дейла) работает за O(E + VC) — линейно. Для монотонных приоритетов (а в Дейкстре извлекаемые расстояния монотонно не убывают) годится радикс-куча с O(E + V log C).

Очень много таймеров с частой отменой. Куча даёт O(log n) на вставку и O(n) на поиск для отмены. Иерархическое таймерное колесо (Varghese & Lauck, 1987) даёт O(1) на вставку, отмену и продвижение времени, ценой ограниченного разрешения. Именно поэтому ядро Linux использует колёса для обычных таймеров, а Kafka переписал свой DelayedOperationPurgatory с кучи на иерархическое колесо — при сотнях тысяч отложенных операций логарифм на вставку стал узким местом.

Нужен порядок, а не только минимум. Планировщик Linux CFS хранит задачи в красно-чёрном дереве по vruntime, а не в куче: ему нужно уметь удалять произвольную задачу (она заснула) и обходить в порядке. Redis реализует sorted set как скиплист + хеш-таблицу: ZRANGEBYSCORE и ZRANK куча не умеет в принципе. Поэтому очереди задач вроде Sidekiq и Celery держат отложенные задания в Redis ZSET, а не в куче — им нужны удаление по id и персистентность.

Нужна стабильность или честность. Куча не сохраняет FIFO среди равных приоритетов и допускает голодание низкоприоритетных задач. Первое чинится составным ключом (priority, sequence_number), второе — старением (постепенное повышение приоритета ждущих задач), многоуровневыми очередями с обратной связью или weighted fair queueing.

Многопоточный доступ. Обычная куча под мьютексом становится точкой сериализации. Здесь нужны конкурентные приоритетные очереди (SprayList, релаксированные очереди) или шардирование по потокам — тема конкурентных структур.

Типичные ошибки

1. Мутация ключа элемента, уже лежащего в куче. Самая коварная. Свойство порядка ломается молча, pop начинает возвращать не минимум, а тесты проходят — потому что на маленьких данных дерево слишком низкое, чтобы ошибка проявилась. Правило: элемент в куче иммутабелен; хотите изменить приоритет — вызывайте decrease_key/heap.Fix или используйте ленивое удаление.

2. Несравнимая нагрузка в кортеже. В Python heappush(h, (priority, task)) упадёт с TypeError: '<' not supported, как только два элемента получат равный приоритет и Python попробует сравнить task. Лечится монотонным счётчиком, который заодно даёт FIFO среди равных:

import itertools
counter = itertools.count()
heapq.heappush(pq, (priority, next(counter), task))  # счётчик разрывает ничьи детерминированно

3. Ожидание, что итерация по куче даст порядок. list(heap) и цикл по PriorityQueue в Java возвращают элементы в произвольном порядке — гарантирован только корень. Единственный отсортированный вывод — последовательные pop.

4. Построение через n × push. Θ(n log n) там, где heapify даёт Θ(n).

5. Max-куча через отрицание на неподходящих типах. Трюк heappush(h, -x) ломается на строках и кортежах, а на целых упирается в асимметрию дополнительного кода: -INT_MIN переполняется. Безопаснее обёртка с инвертированным __lt__ или functools.total_ordering.

6. Неограниченный рост при ленивом удалении. Если отмены часты, куча может состоять из мусора на 90%. Считайте долю мёртвых записей и пересобирайте кучу через heapify, когда она превысит порог.

7. remove(Object) в Java PriorityQueue. Это O(n) — линейный поиск. Вызов в цикле превращает алгоритм в квадратичный. Аналогично: in по списку-куче в Python.

8. Неограниченная куча в стриминге. Для top-k держите ровно k элементов (heapreplace), а не «положим всё, потом отсортируем» — иначе OOM на большом потоке.

9. Путаница имён в heapq. В исходниках CPython _siftdown(heap, startpos, pos) поднимает элемент вверх, а _siftup(heap, pos) опускает его вниз — ровно наоборот к учебной терминологии. Имена отражают направление движения «дырки», а не элемента. Если вы читаете исходник модуля, держите это в голове.

Кучи в стандартных библиотеках

Минимальный пример на Go — потому что container/heap устроен непривычно и его стоит увидеть:

// Item — элемент очереди. Поле index нужно, чтобы heap.Fix нашёл элемент за O(1).
type Item struct {
    Value    string
    Priority int
    index    int // позиция в куче; поддерживается в актуальном состоянии методом Swap
}

type PQ []*Item

func (pq PQ) Len() int           { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].Priority < pq[j].Priority } // min-куча
func (pq PQ) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index, pq[j].index = i, j // критично: без этого heap.Fix сломается
}

func (pq *PQ) Push(x any) {
    it := x.(*Item)
    it.index = len(*pq)
    *pq = append(*pq, it)
}

func (pq *PQ) Pop() any {
    old := *pq
    it := old[len(old)-1]
    old[len(old)-1] = nil // помогаем сборщику мусора
    it.index = -1         // элемент больше не в куче
    *pq = old[:len(old)-1]
    return it
}

// Использование: decrease_key делается изменением поля плюс heap.Fix.
//   it.Priority = 1
//   heap.Fix(pq, it.index)  // O(log n)

Здесь виден главный подводный камень container/heap: если вы измените Priority и забудете heap.Fix, куча тихо сломается. Компилятор вам не поможет.

Мини-итог

• Приоритетная очередь — это АТД («кто следующий?»), куча — самая частая его реализация. Не путайте их: у одного АТД десяток реализаций с разными профилями стоимости.
• Бинарная куча = свойство порядка (родитель ≤ детей) + свойство формы (полное дерево). Форма позволяет уложить дерево в массив без единого указателя — отсюда память и локальность.
• Всё сводится к двум процедурам: sift_up после вставки в конец, sift_down после замены корня последним листом. Обе O(log n).
• heapify снизу вверх стоит Θ(n), а не Θ(n log n) — потому что дешёвых узлов экспоненциально больше, чем дорогих. Никогда не стройте кучу циклом push’ей.
• heapsort даёт гарантированный O(n log n) при O(1) памяти, но проигрывает по кешу. Живёт в проде как fallback внутри introsort/pdqsort.
• decrease_key требует знать позицию элемента: либо индексированная куча с хеш-таблицей, либо ленивое удаление. Второе проще, асимптотику не портит и потому побеждает почти всегда.
• Фибоначчиева куча лучше на бумаге и хуже на практике; парные и 4-арные кучи выигрывают на реальном железе.
• Куча — неправильный выбор, если нужны запросы по диапазону, порядок среди равных, частая отмена, или если приоритеты — малые целые (там бакеты и таймерные колёса дают O(1)).

Источники

• CLRS, гл. 6 «Heapsort» и гл. 19 «Fibonacci Heaps» — строгий вывод оценок: mitpress.mit.edu
• Sedgewick & Wayne, Algorithms, §2.4 «Priority Queues» — образцовый разбор с кодом и индексированной очередью: algs4.cs.princeton.edu/24pq
• Skiena, The Algorithm Design Manual, §3.5 и §4.3: algorist.com
• Williams, J. W. J. Algorithm 232: Heapsort, CACM 1964 — оригинальная публикация: doi.org/10.1145/512274.512284
• Floyd, R. W. Algorithm 245: Treesort 3, CACM 1964 — построение кучи за O(n): doi.org/10.1145/355588.365103
• Fredman & Tarjan, Fibonacci Heaps and Their Uses, JACM 1987: doi.org/10.1145/28869.28874
• Larkin, Sen & Tarjan, A Back-to-Basics Empirical Study of Priority Queues, 2014 — почему простые кучи побеждают: arxiv.org/abs/1403.0252
• Fredman, Sedgewick, Sleator & Tarjan, The Pairing Heap, Algorithmica 1986: doi.org/10.1007/BF01840439
• Haeupler, Sen & Tarjan, Rank-Pairing Heaps, SIAM J. Comput. 2011: doi.org/10.1137/100785351
• Varghese & Lauck, Hashed and Hierarchical Timing Wheels, SOSP 1987: doi.org/10.1145/41457.37504
• Python heapq — документация и исходник с отличными комментариями: docs.python.org/3/library/heapq.html, github.com/python/cpython/blob/main/Lib/heapq.py
• Go container/heap: pkg.go.dev/container/heap
• Boost.Heap — сравнение реализаций в одной таблице: boost.org/doc/libs/release/doc/html/heap.html
• Apache Kafka, Purgatory и переход на иерархические таймерные колёса: cwiki.apache.org
• Rust BinaryHeap: doc.rust-lang.org/std/collections/struct.BinaryHeap.html

Что дальше

Куча выжимает максимум из предположения «ключи можно только сравнивать». Но у ключей часто есть внутренняя структура, и её грех не использовать. Строка — это не атомарное значение, а последовательность символов с общими префиксами; на этом строится совсем другая геометрия поиска, где стоимость операции зависит от длины ключа, а не от размера множества.

Следующая статья: Префиксные деревья, суффиксные массивы и строковые структуры — разберём trie и сжатые радикс-деревья, суффиксные массивы с LCP, автоматы Ахо — Корасик и то, как всё это работает в автодополнении, маршрутизаторах и полнотекстовом поиске.

Общая карта трека — в обзоре.