Приоритетная очередь

Приоритетная очередь - структура с тремя операциями: добавить элемент, посмотреть максимум, извлечь максимум. Реализуется кучей, все три операции - $O(\log n)$, а просмотр максимума и вовсе $O(1)$.

Добавление и извлечение

Добавление: кладём элемент в конец массива и просеиваем вверх.

Извлечение: запоминаем корень, переносим последний элемент в корень, уменьшаем размер и просеиваем вниз.

int push(int value) { a[++size] = value; return sift_up(a, size); }

pair<int, int> pop() {                    // {куда уехал последний, что извлекли}
    int top = a[1];
    if (size == 1) { size = 0; return {0, top}; }
    a[1] = a[size--];
    return {sift_down(a, 1, size), top};
}

Случай размера 1 стоит выписать отдельно: просеивать нечего, и «куда уехал элемент» - вопрос без ответа.

Удаление произвольного элемента

Схема та же, что при извлечении: на место удаляемого ставим последний элемент и уменьшаем размер. Но дальше - развилка: новый элемент может оказаться и больше родителя, и меньше детей, смотря что там было.

Универсальный рецепт: просеять вверх; если элемент не сдвинулся - просеять вниз.

a[i] = a[size--];
if (sift_up(a, i) == i) sift_down(a, i, size);

Соблазн обойтись одним просеиванием силён, и он ошибочен. Измерено на 147 978 случайных удалениях из случайных куч:

что делали	куча оказалась сломана
оба просеивания	0 раз
только вверх	45 213 раз
только вниз	2 702 раза

При этом реально что-то двигается редко: просеивание вверх сработало 2 702 раза, вниз - 45 213, а в 100 063 случаях элемент остался на месте. То есть лишнее просеивание почти ничего не стоит, а его отсутствие ломает кучу в каждом третьем удалении.

Заметьте симметрию в таблице: «только вверх» ломается ровно там, где нужно было вниз, и наоборот. Это не совпадение - ровно одно из двух просеиваний делает работу.

Чего не умеет std::priority_queue

нужно	std::priority_queue
добавить, посмотреть и извлечь максимум	умеет
изменить приоритет лежащего элемента	нет
удалить произвольный элемент	нет
узнать, где лежит элемент	нет
обойти содержимое	нет
ограничить вместимость	нет

Отсюда три обхода, и выбирать между ними стоит осознанно.

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

Ленивое удаление. Кладём в очередь новые версии, а старые помечаем устаревшими и выбрасываем при извлечении. Куча растёт, зато код короче. Так обычно и пишут Дейкстру.

std::set вместо кучи. Умеет всё, включая удаление по значению и обход, но с большей константой и без дубликатов (для них нужен multiset).

Про вместимость и дубликаты

Две вещи, о которых в учебниках обычно молчат, а в задачах спрашивают.

Ограниченная вместимость. Если очередь полна, добавление должно отказать - и не изменить кучу. Легко случайно увеличить размер до проверки; тогда структура портится молча.

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

Где куча решает задачу

задача	как
$k$ наибольших в потоке	min-куча размера $k$: пришло больше корня - заменяем
медиана потока	две кучи: max-куча на левую половину, min-куча на правую
слияние $k$ отсортированных списков	куча из голов списков
наименьшая стоимость склейки	каждый раз склеиваем две наименьшие
планирование с дедлайнами	берём всё подряд, при переполнении выбрасываем худшее

Общий признак: в жадном алгоритме на каждом шаге нужен экстремум изменяющегося множества. Если множество не меняется - хватит сортировки; если меняется - нужна куча.