Уменьшение ключа и удаление: чего куче не хватает

Если ты умеешь и вести словарь позиций с обновлением при обменах, и писать ленивый вариант с отбрасыванием устаревших записей, и объяснить, чем платит каждый, листай до «Теперь сам».

Как думаешь, почему это вообще проблема

В очереди лежит вершина v с оценкой расстояния 17. Алгоритм нашёл путь покороче - 9. Прежде чем читать дальше, прикинь, как это сделать в куче. Пройти массив и найти v - O(n), и весь смысл логарифмической очереди пропал. Держать элементы отсортированными - это уже не куча. Вот в этом зазоре и живёт вся тема: структура, отвечающая на вопрос «кто самый срочный», не отвечает на вопрос «где лежит вот этот конкретный».

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

Стопка заявок, разложенная так, что самая срочная всегда сверху. Пришло уточнение: заявка Петрова стала срочнее. Чтобы переложить её, надо сначала НАЙТИ её в стопке - а стопка не алфавитная, придётся перебрать. Два выхода. Первый: завести рядом тетрадку «Петров - страница 43» и честно править её при каждом перекладывании листов; тетрадка стоит труда и рвётся, если забыть запись. Второй: не искать вовсе - положить сверху новый лист с уточнённой срочностью, а старый, когда до него дойдёт очередь, узнать по отметке и выбросить. Второй способ тратит бумагу и экономит нервы.

Механизм: словарь позиций против ленивого удаления

Честный способ. Куча хранит ещё и pos - куда уехал каждый элемент:

# min-куча, элементы - номера вершин, ключи - в массиве key[]
обменять(i, j):
    heap[i], heap[j] = heap[j], heap[i]
    pos[heap[i]] = i           # ОБА обновления обязательны,
    pos[heap[j]] = j           # и делать их надо внутри обмена, а не рядом с ним

decrease_key(v, new):
    если new >= key[v]: выход      # уменьшать можно только вниз
    key[v] = new
    просеять_вверх(pos[v])         # знаем позицию - сразу чиним, O(log n)

удалить(v):
    i = pos[v]
    обменять(i, len(heap) - 1)
    heap.pop()
    удалить pos[v]                 # иначе словарь показывает в уже отрезанный хвост
    если i < len(heap):            # удаляли не последний элемент - есть что чинить
        просеять_вниз(i)           # на месте i теперь ДРУГОЙ элемент: он мог оказаться
        просеять_вверх(i)          # и больше, и меньше прежнего, поэтому чиним в обе
                                   # стороны; сработает ровно одна из них - если элемент
                                   # опустился, он уже не меньше родителя, и наоборот

Ленивое удаление (оно же ленивое обновление) - второй способ: кучу не трогаем вовсе, а устаревшие записи отбрасываем при извлечении.

улучшить(v, new):
    если new < dist[v]:
        dist[v] = new
        push((new, v))             # старая запись остаётся в куче и станет мусором

извлечь_актуальный():
    пока куча не пуста:
        (d, v) = pop()
        если d == dist[v]:         # запись свежая - её и возвращаем
            вернуть (d, v)
        # иначе это устаревший дубль - молча пропускаем

Цена: в куче до m записей вместо n (m - число улучшений), то есть память O(m) и логарифм от m вместо логарифма от n. Для графа это log m <= log(E) <= 2·log(V) - разница в константу, и на практике ленивый вариант обычно быстрее честного, потому что не платит за поддержку словаря на каждом обмене.

Правило

Куча не знает позиций своих элементов, поэтому decrease_key требует внешнего словаря pos[элемент] = индекс, обновляемого ВНУТРИ обмена; тогда уменьшение ключа - O(log n), а удаление произвольного элемента - замена последним и просеивание в ОБЕ стороны. Альтернатива - ленивое обновление: класть новую запись и отбрасывать устаревшие при извлечении, сверяя приоритет записи с актуальным. Ленивый вариант проще и обычно быстрее, платит памятью O(числа вставок).

Разбор: уменьшаем ключ в min-куче

Min-куча ключей: [2, 7, 5, 12, 9, 6, 8] (индексы 0..6), и пусть элемент с ключом 12 лежит в ячейке 3, а словарь говорит pos[D] = 3. Уменьшаем ключ D с 12 до 1.

1. key[D] = 1, массив: [2, 7, 5, 1, 9, 6, 8]. Свойство нарушено: родитель 7 больше ребёнка 1.
2. Просеиваем вверх от i = 3. Родитель (3−1)//2 = 1, там 7. 7 > 1 - обмен. Массив: [2, 1, 5, 7, 9, 6, 8]. Обновляем словарь: pos[D] = 1, pos[элемента с ключом 7] = 3.
3. i = 1, родитель 0, там 2. 2 > 1 - обмен. Массив: [1, 2, 5, 7, 9, 6, 8]. Снова правим словарь: pos[D] = 0, pos[элемента с ключом 2] = 1.
4. i = 0 - корень, стоп.

Два обмена, O(log n). Главное в разборе - не обмены, а ЧЕТЫРЕ обновления словаря: при каждом обмене меняются позиции ОБОИХ участников. Пропустишь одно - словарь начнёт врать, и следующий decrease_key починит чужой узел; куча при этом останется формально корректной, а алгоритм даст неверный ответ. Ошибка не падает и не видна в тестах на маленьких графах.

Разбор: ленивая Дейкстра на трёх шагах

Пусть dist[B] сначала 17, и в куче лежит запись (17, B). Потом нашёлся путь 9: кладём (9, B), dist[B] = 9. В куче теперь две записи про B. Что произойдёт дальше:

1. pop() достаёт (9, B) - это минимум. Проверка: 9 == dist[B]? Да - запись свежая, вершину обрабатываем, помечаем как готовую.
2. Позже pop() достаёт (17, B). Проверка: 17 == dist[B] (а там 9)? Нет - запись устарела, молча пропускаем и берём следующую. Никакого поиска, никакого удаления.
3. Почему это корректно: свежая запись всегда имеет меньший приоритет, чем устаревшая, а значит выходит из кучи РАНЬШЕ неё. К моменту, когда наверх всплывёт мусор, вершина уже обработана, и пропустить его безопасно.

Цена видна тут же: куча хранила две записи вместо одной. В худшем случае записей столько, сколько было улучшений, то есть O(E) для графа. Зато в коде нет ни словаря позиций, ни обмена с обновлением - только push и проверка одной строкой при pop.

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

Первое: обновлять pos не внутри обмена, а «где-то рядом» - рано или поздно найдётся путь, где обмен есть, а обновления нет. Обновление обязано жить в той же функции, что и обмен. Второе: decrease_key, который на самом деле увеличивает ключ, - просеивание вверх тогда не помогает, нужно вниз; поэтому в честной реализации проверяют направление, а лучше держат две отдельные операции. Третье: ленивый вариант без проверки при извлечении - очередь начнёт возвращать отменённые и устаревшие записи - не сразу, а когда свежие кончатся: приоритет у мусора хуже, поэтому он всплывает последним и тем опаснее, что до него доходит уже в конце работы. Четвёртое: ленивое удаление без ограничения роста - в долгоживущей очереди (таймеры, события) мусор копится и съедает память; лечится либо периодической пересборкой кучи за O(n), либо счётчиком мусора с порогом. Пятое: хранить в куче объекты, приоритет которых меняют снаружи, - структура об изменении не узнает и свойство кучи нарушится незаметно для всех.

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

Дейкстра и Прим - главные потребители: обе формулируются как «взять ближайшую вершину и улучшить оценки соседей», и вторая половина фразы - это и есть decrease_key. От того, сколько он стоит, зависит итоговая оценка алгоритма: с двоичной кучей Дейкстра стоит O((V+E)·log V), с кучей Фибоначчи - O(E + V·log V) (следующая глава). Планировщики и таймеры сталкиваются с той же задачей под другим именем: «отменить таймер» и «перевести задачу в другой приоритет» - это удаление и изменение ключа. В ядре Linux НИЗКОТОЧНЫЕ таймеры (timer_list) живут не в куче, а в колесе таймеров именно потому, что постановка и отмена должны быть O(1); высокоточные (hrtimer) хранятся в красно-чёрном дереве, и там отмена - O(log n). Практический совет: начинай с ленивого варианта - он проще, реже ломается и обычно быстрее; переходи к словарю позиций, когда память под мусор становится проблемой или когда удаление нужно честное и немедленное.

Теперь сам

В ленивой очереди лежат записи (4, X), (9, Y), (6, Y), (7, Z), а актуальные оценки - dist[X] = 4, dist[Y] = 6, dist[Z] = 7. Что вернут четыре подряд идущих извлечения и сколько записей будет отброшено?