Стабильность, min-куча и кучи с большим ветвлением

Если ты знаешь приём (приоритет, счётчик), умеешь считать высоту и цену операций d-арной кучи и понимаешь, почему на практике берут d = 4, листай до «Теперь сам».

Как думаешь, что вернётся первым

В min-очередь кладут (5, "почта"), (2, "платёж"), (5, "отчёт"). Прежде чем читать дальше, ответь: что вернёт очередь вторым - почту или отчёт? Приоритеты у них равны, и честный ответ - звучит так: предсказать нельзя. Случайности здесь нет - порядок полностью определён историей операций и тем, как легли обмены при просеивании, - но контракт очереди его не гарантирует, и от версии к версии он может смениться. Для очереди, которая обслуживает людей или задачи одной важности, такой ответ не годится, и вопрос «а чем это чинить» - не теоретический.

На что это похоже

Два регистратора. Первый вызывает пациентов строго по тяжести случая, а при равной тяжести - «ну, вот этого, он ближе стоял». Второй при равной тяжести смотрит в талон с номером очереди. Разница только в том, что второй дописал к признаку «тяжесть» второй признак «номер», и сравнение стало однозначным. Структура не изменилась - изменился ключ.

Механизм: три настройки одной структуры

min-куча          : класть −x (вернуть −результат) ИЛИ поменять знак сравнения
                    в просеиваниях; отдельной структуры не нужно

стабильность      : ключ = (приоритет, номер_прихода)
                    сравнение пар: сначала приоритет, при равенстве - счётчик
                    (приоритет, счётчик, объект) - ещё и защита от сравнения объектов

d-арная куча      : дети узла i - ячейки d·i+1 ... d·i+d, родитель (i−1)//d
                    высота log_d n
                    push / decrease_key: log_d n сравнений
                    pop: d·log_d n сравнений (на каждом уровне ищем лучшего из d)

Арифметика ветвления стоит того, чтобы её проговорить. Для n = 10⁶: у двоичной кучи log₂ 10⁶ ≈ 20 уровней, у четырёхарной - log₄ 10⁶ ≈ 10. Вставка становится вдвое короче. А вот извлечение: d·log_d n для d = 2 даёт 2·20 = 40 сравнений, для d = 4 - 4·10 = 40, ровно столько же. Функция d/ln d имеет минимум при d = e ≈ 2.72, то есть по числу сравнений НА ИЗВЛЕЧЕНИИ чуть лучше всех d = 3 (около 38 сравнений на том же миллионе); на смешанном профиле, где есть и вставки, картина другая - её посчитаем ниже. Разница между двойкой, тройкой и четвёркой мала, и решает не она, а память: четыре ребёнка лежат в массиве ПОДРЯД, то есть читаются одной-двумя кеш-линиями вместо четырёх разбросанных чтений, а индексы считаются сдвигами. Оговорка: блок детей в укладке d·i+1 .. d·i+d не выровнен по границе линии сам собой, и реализации, которым это важно, сдвигают массив на несколько ячеек. Поэтому в реальных реализациях (например, в очередях внутри некоторых планировщиков и в библиотеках для Дейкстры на больших графах) встречается именно d = 4.

Правило

Куча не стабильна - при равных приоритетах порядок прихода не сохраняется; ключ-пара (приоритет, счётчик) делает её стабильной и заодно не даёт сравнению дойти до объектов. Min-куча - это max-куча с отрицанием ключа или обратным сравнением. В d-арной куче дети узла i - это d·i+1 .. d·i+d, родитель (i−1)//d, высота log_d n: вставка и уменьшение ключа дешевеют в log₂ d раз, извлечение стоит d·log_d n сравнений. Минимум по сравнениям НА ИЗВЛЕЧЕНИИ - около d = 3, на смешанном профиле обычно выигрывает d = 4, а на реальном железе - оно же из-за кеша.

Разбор: делаем очередь стабильной

Заявки с приоритетами (2, "A"), (1, "B"), (2, "C"), (1, "D") приходят в этом порядке, извлекаем по возрастанию приоритета. Наивная min-куча вернёт сначала обе единицы, но B и D в непредсказуемом порядке. Делаем ключ парой, номера по порядку поступления: A → (2, 1), B → (1, 2), C → (2, 3), D → (1, 4). Теперь сравнение пар лексикографическое, и порядок извлечения определён однозначно: (1, 2) - B, (1, 4) - D, (2, 1) - A, (2, 3) - C.

Второй эффект того же приёма чаще всего и оказывается причиной, по которой его добавляют. Если в очередь кладут пары (приоритет, объект), а у объектов не определено сравнение, то при РАВНЫХ приоритетах интерпретатор полезет сравнивать сами объекты и упадёт - причём не сразу, а на первом входе, где приоритеты совпали. Счётчик посередине - (приоритет, счётчик, объект) - гарантирует, что до объекта сравнение никогда не дойдёт: два счётчика не бывают равны.

Считаем вместе: четырёхарная куча на миллионе элементов

Пусть в очереди всё время около n = 10⁶ элементов, а за время работы её просят об этом: 10 миллионов УМЕНЬШЕНИЙ КЛЮЧА и 1 миллион извлечений. Так выглядит честная Дейкстра со словарём позиций: вершин в очереди V = 10⁶, извлекают каждую по разу, а улучшать оценки приходится до одного раза на ребро. Уменьшение ключа просеивает элемент ВВЕРХ - той же ценой, что вставка. Считаем по худшему случаю: в отличие от случайной вставки из первого урока, здесь элемент всплывает целенаправленно, и короткие подъёмы обещать нельзя.

d = 2:  высота 20
        уменьшения ключа: 10 млн × 20     = 200 млн сравнений
        извлечения:        1 млн × 2 × 20 =  40 млн сравнений
        итого ≈ 240 млн

d = 4:  высота 10
        уменьшения ключа: 10 млн × 10     = 100 млн сравнений
        извлечения:        1 млн × 4 × 10 =  40 млн сравнений
        итого ≈ 140 млн

Экономия - в 1,7 раза (240 против 140, то есть минус 42%), и вся она на подъёмах, потому что именно они выигрывают от низкого дерева, а извлечения остаются при своих. Отсюда правило выбора: чем сильнее перекос в сторону вставок и уменьшений ключа, тем больше выгодно ветвление. При обратном перекосе (извлечений столько же, сколько вставок) разница между d = 2 и d = 4 по сравнениям исчезает, и остаётся только выигрыш по кешу. Заметь, что асимптотика при этом не изменилась ни на букву: log_d n и log₂ n отличаются константой log₂ d. Это тот случай, когда решение принимают по константам, и это нормальная инженерная работа, а не «микрооптимизация».

Что ломается без этого

Первое: при отрицании ключа для min-кучи забыть отрицать счётчик - стабильность превратится в свою противоположность, вперёд полезет тот, кто пришёл позже. Второе: считать, что (приоритет, объект) безопасно, - пока приоритеты различны, всё работает, а на первом совпадении программа падает или сравнивает объекты неожиданным образом. Третье: в d-арной куче перепутать формулы индексов - d·i+1 .. d·i+d и (i−1)//d; двоичные 2i+1 и (i−1)//2 - их частный случай при d = 2, и смешение источников даёт кучу, которая теряет элементы. Четвёртое: брать большое d (16, 32) «чтобы дерево было ещё ниже» - извлечение становится линейным по d на каждом уровне, и выигрыш съедается. Пятое: ждать стабильности от библиотечной очереди по умолчанию - её не дают ни heapq, ни std::priority_queue. Разница лишь в том, что документация heapq говорит об этом прямо и предлагает тот самый приём со счётчиком, а стандарт C++ про стабильность priority_queue просто молчит - её там нет и обещано не было.

Зачем это в работе

Стабильность нужна везде, где очередь обслуживает людей или задачи равной важности: заявки в техподдержке, задачи в планировщике, сообщения одного приоритета. Ключ-пара - стандартный ответ, и в документации heapq он приведён как рекомендуемый приём. Выбор ветвления - рабочий инструмент для больших графов: если Дейкстра на миллионах рёбер не укладывается во время, переход на четырёхарную кучу даёт заметное ускорение без смены алгоритма. Более общий навык, который стоит унести: структура данных - не монолит, у неё есть ПАРАМЕТРЫ (направление сравнения, состав ключа, ветвление), и настраивают их под профиль операций. Прежде чем менять алгоритм, посчитай, сколько у тебя операций каждого вида, - иногда ответ в том, чтобы подкрутить константу, а не переписывать всё.

Теперь сам

Профиль: n = 10⁶ элементов, 2 миллиона вставок и 2 миллиона извлечений. Посчитай сравнения для d = 2 и d = 4 и скажи, какое ветвление выгоднее по сравнениям.