Монотонная приоритетная очередь

Абстрактный тип данных в информатике

В информатике монотонная приоритетная очередь — это вариант абстрактного типа данных приоритетной очереди , в котором приоритеты извлеченных элементов должны формировать монотонную последовательность . То есть для приоритетной очереди, в которой каждый последовательно извлеченный элемент имеет минимальный приоритет (min-heap), минимальный приоритет должен монотонно увеличиваться. Наоборот, для max-heap максимальный приоритет должен монотонно уменьшаться. Предположение о монотонности естественным образом возникает в нескольких приложениях приоритетных очередей и может использоваться в качестве упрощающего предположения для ускорения определенных типов приоритетных очередей. ^[1]^{: 128}

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

Приложения

Монотонные очереди приоритетов возникают естественным образом при упорядочивании событий по времени, например, сетевые тайм-ауты или дискретное моделирование событий . Событие может привести к тому, что какое-то действие будет запланировано на некоторое время в будущем, но (реальная или смоделированная) причинность делает попытки запланировать действия в прошлом бессмысленными.

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

Аналогично, в алгоритмах развертки линии в вычислительной геометрии события, в которых развертка линии пересекает интересующую точку, имеют приоритет по координате точки пересечения, и эти события извлекаются в монотонном порядке. Монотонный порядок извлечения также встречается в версии наилучшего первого ветвления и границы . ^[1]^{: 128}

Структуры данных

Любая приоритетная очередь, которая может обрабатывать немонотонные операции извлечения, может также обрабатывать монотонные извлечения, но некоторые приоритетные очереди специализированы для работы только с монотонными извлечениями или работают лучше, когда извлечения монотонны. Например, очередь контейнеров представляет собой простую структуру данных приоритетной очереди, состоящую из массива, индексированного по приоритету, где каждая ячейка массива содержит контейнер элементов с этим приоритетом. Операция извлечения-min выполняет последовательный поиск первого непустого контейнера и выбирает произвольный элемент в этом контейнере. Для немонотонных извлечений каждая операция извлечения-min занимает время (в худшем случае), пропорциональное длине массива (количеству различных приоритетов). Однако при использовании в качестве монотонной приоритетной очереди поиск следующего непустого контейнера может начинаться с приоритета самой последней предыдущей операции извлечения-min, а не с начала массива. Эта оптимизация приводит к тому, что общее время для последовательности операций пропорционально сумме количества операций и длины массива, а не (как в немонотонном случае) произведению этих двух величин. ^[2]

Cherkassky, Goldberg & Silverstein (1999) описывают более сложную схему, называемую очередью Heap-on-top (HOT) для монотонных приоритетных очередей с целочисленными приоритетами, основанную на многоуровневом сегментировании вместе с обычной очередью с приоритетами кучи. Используя этот метод, они получают структуру, которая может поддерживать элементы с целочисленными приоритетами в диапазоне от $0$ до параметра $C.$ Горячая очередь использует постоянное время на операцию вставки или уменьшения приоритета и амортизированное время на операцию извлечения минимума. ^[3] Другая связанная структура Рамана (1996) позволяет приоритетам быть целыми числами машины и снова допускает операции вставки и уменьшения приоритета с постоянным временем, с операциями извлечения минимума в приоритетной очереди из $n$ элементов, требующими амортизированного времени . ^[4] Эти результаты приводят к соответствующему ускорению в алгоритме Дейкстры для графов с целочисленными весами ребер. $O((\log C)^{1/3}(\log \log C)^{1/2})$ $O({\sqrt {\log n\log \log n}})$

Ссылки

^ ab Mehlhorn, Kurt ; Sanders, Peter (2008). "Приоритетные очереди" (PDF) . Алгоритмы и структуры данных: базовый набор инструментов. Springer.
^ Скиена, Стивен С. (1998), Руководство по разработке алгоритмов, Springer, стр. 181, ISBN 978-0-387-94860-7.
^ Черкасский, Борис В.; Голдберг, Эндрю В .; Сильверстайн, Крейг (август 1999 г.), «Ведра, кучи, списки и монотонные приоритетные очереди», SIAM Journal on Computing , 28 (4): 1326–1346 (электронный), CiteSeerX 10.1.1.49.8244 , doi :10.1137/S0097539796313490, MR 1681014 .
^ Раман, Раджив (1996), «Очереди с приоритетами: малые, монотонные и трансдихотомические», Алгоритмы — ESA '96 (Барселона) , Конспект лекций по информатике, т. 1136, Берлин: Springer, стр. 121–137 , doi :10.1007/3-540-61680-2_51, ISBN 978-3-540-61680-1, MR 1469229, S2CID 17004419.

[mehlhorn-1] Mehlhorn, Kurt ; Sanders, Peter (2008). "Приоритетные очереди" (PDF) . Алгоритмы и структуры данных: базовый набор инструментов. Springer.

[2] Скиена, Стивен С. (1998), Руководство по разработке алгоритмов, Springer, стр. 181, ISBN 978-0-387-94860-7.

[3] Черкасский, Борис В.; Голдберг, Эндрю В .; Сильверстайн, Крейг (август 1999 г.), «Ведра, кучи, списки и монотонные приоритетные очереди», SIAM Journal on Computing , 28 (4): 1326–1346 (электронный), CiteSeerX 10.1.1.49.8244 , doi :10.1137/S0097539796313490, MR 1681014 .

[4] Раман, Раджив (1996), «Очереди с приоритетами: малые, монотонные и трансдихотомические», Алгоритмы — ESA '96 (Барселона) , Конспект лекций по информатике, т. 1136, Берлин: Springer, стр. 121–137 , doi :10.1007/3-540-61680-2_51, ISBN 978-3-540-61680-1, MR 1469229, S2CID 17004419.