Конспект раздела: кучи и непересекающиеся множества

Понятия

Очередь с приоритетами - контракт: push, peek, pop экстремума, build. Реализация решает цену, контракт решает пригодность. Двоичная куча: O(log n) / O(1) / O(log n) / O(n).

Просеивание вверх - вставка: элемент в конец массива, потом наверх, пока больше родителя (в max-куче раздела; в min-куче - пока меньше). Одно сравнение на уровень (у просеивания вниз - два).

decrease_key - куча не знает позиций своих элементов, поэтому нужен словарь pos (обновлять ВНУТРИ обмена) или ленивая запись с отбрасыванием устаревших при извлечении.

Стабильность - её нет; даёт ключ-пара (приоритет, счётчик), она же спасает от сравнения объектов.

d-арная куча - дети d·i+1 .. d·i+d, родитель (i−1)//d, высота log_d n: дешевеют вставки, снятие остаётся при своих (d·log_d n).

Сливаемые кучи - лес деревьев на указателях вместо одного дерева в массиве. Биномиальная: деревья B_k по 2^k узлов, их набор повторяет двоичную запись n, слияние - сложение с переносом. Фибоначчи: ленивое сцепление корней, разрез вместо просеивания, уплотнение при extract_min, правило одной потери и каскадный разрез, степень ≤ 1.44·log₂ n.

Union-find - лес представителей: parent[x], корень = представитель, «в одной ли группе» - сравнение find. Объединение по рангу даёт O(log n), плюс сжатие пути - амортизированное O(α(n)), где α - обратная функция Аккермана (не коэффициент заполнения из раздела 7).

Что унести

Цена операций:

Два доказательства из раздела стоит уметь воспроизводить:

дерево ранга r держит ≥ 2^r узлов  → r ≤ log₂ n
   (ранг растёт только при слиянии РАВНЫХ, то есть при удвоении)

поддерево узла степени k в куче Фибоначчи содержит ≥ F_(k+2) ≥ φ^k узлов → k ≤ 1.44·log₂ n
   (правило одной потери: вторая потеря отрезает сам узел)

Сквозная мысль раздела - ленивость: не делай работу, которую можно отложить, и прибирайся там, куда всё равно пришёл. Куча Фибоначчи откладывает уплотнение до extract_min; ленивая очередь не удаляет записи, а помечает; union-find не перекрашивает группу, а чинит путь при ближайшем find. Обратная сторона той же мысли - ослабление формы покупает операцию: двоичная куча быстра и компактна, потому что держит форму полного дерева, и по той же причине не умеет сливаться.

Практические выводы, которые расходятся с учебником: - куча Фибоначчи в прикладном коде редкость; чаще выигрывает двоичная куча с ленивым удалением или спаривающаяся куча; - прежде чем менять структуру, проверь ПОРЯДОК операций: слить k равных списков цепочкой - Θ(N·k), турниром - Θ(N·log k), а слияние в обоих случаях одно и то же; - union-find пишут сразу с обеими оптимизациями: это три строки, после которых структура перестаёт быть узким местом.

Ошибки, которые не падают, а тихо портят результат: забытое обновление pos при обмене; ленивое извлечение без сверки приоритета; подвешивание корней без сравнения рангов; попытка разъединить множества.

Куда это ведёт

Обе структуры - рабочие детали графовых алгоритмов. Дейкстра и Прим стоят на очереди с приоритетами (O((V+E)·log V) на двоичной куче, O(E + V·log V) на куче Фибоначчи - разница видна на плотных графах). Крускал стоит на union-find, и там структура дешевле сортировки рёбер. Следующий раздел - представление графов и обход в глубину.