# конспект · шаг 6 из 6
Конспект: очередь с приоритетами
Понятия
Очередь с приоритетами - контракт, а не структура: push(x), peek() (посмотреть экстремум),
pop() (забрать экстремум), build(a). Реализаций много; от выбора зависит только цена.
Двоичная куча как реализация: push и pop - O(log n), peek - O(1), build - O(n).
Сама куча (полное дерево в массиве, дети 2i+1 и 2i+2, родитель (i−1)//2, просеивание вниз)
разобрана в разделе про сортировки; здесь она рассмотрена как долгоживущая структура.
Просеивание вверх (sift-up) - вставка: элемент кладут в КОНЕЦ массива (единственная позиция, где полное дерево остаётся полным) и меняют с родителем, пока он больше. Одно сравнение на уровень против двух при просеивании вниз.
decrease_key - уменьшение приоритета лежащего в очереди элемента. Куча сама не знает его
позиции (поиск по ключу - O(n)), поэтому нужен один из двух приёмов:
| приём | цена | чем платит |
|---|---|---|
словарь pos[элемент] = индекс |
decrease_key O(log n) |
обновление ВНУТРИ обмена; ошибка портит структуру молча |
| ленивая запись | push O(log m) |
куча растёт до числа вставок; при pop сверять приоритет с актуальным |
Удаление произвольного элемента (позиция известна): заменить последним, укоротить массив, просеять в ОБЕ стороны - новый элемент мог оказаться и больше, и меньше прежнего.
Стабильность - куча её не даёт. Ключ-пара (приоритет, счётчик) восстанавливает порядок
прихода при равных приоритетах и заодно не даёт сравнению дойти до объектов.
d-арная куча - ветвление d вместо двух: дети d·i+1 .. d·i+d, родитель (i−1)//d, высота
log_d n. Вставка - log_d n сравнений, снятие - d·log_d n.
Что унести
контракт решает, подходит ли структура; реализация решает, сколько это стоит
Цена операций у двоичной кучи:
| операция | цена | замечание |
|---|---|---|
peek |
O(1) |
экстремум в корне |
push |
O(log n) |
одно сравнение на уровень; на случайных данных в среднем O(1) |
pop |
O(log n) |
два сравнения на уровень; путь обычно почти полный |
build |
O(n) |
готовый массив превращают в кучу, а не наполняют циклом push |
| поиск по ключу | O(n) |
куча не дерево поиска |
| слияние двух куч | O(n) |
дешёвого слияния нет - это следующая глава |
Ветвление выгодно там, где вставок много больше, чем снятий: d = 4 вдвое укорачивает дерево и
кладёт четырёх детей в одну кеш-линию, а снятие при этом не дорожает (4·log₄ n = 2·log₂ n).
Минимум по числу сравнений - около d = 3, разница мала, решает память.
Выбор способа изменения приоритета: начинай с ленивого - он проще, реже ломается и обычно быстрее; переходи к словарю позиций, когда мусор в очереди становится проблемой по памяти или когда удаление нужно честное и немедленное.
Три ошибки, которые не падают, а тихо портят результат: забытое обновление pos при обмене;
ленивое извлечение без сверки приоритета; изменение приоритета объекта СНАРУЖИ кучи.
Куда это ведёт
Дейкстра и Прим - главные потребители контракта: «взять ближайшую вершину» - это pop, «улучшить
оценки соседей» - это decrease_key. С двоичной кучей Дейкстра стоит O((V+E)·log V). Уменьшить
вклад decrease_key до O(1) умеет куча Фибоначчи - о ней и о дешёвом слиянии следующая глава.
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий