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

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

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

Приложения

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

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

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

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

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

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

Ссылки

^ Перейти обратно: ^а ^б Мельхорн, Курт ; Сандерс, Питер (2008). «Приоритетные очереди» (PDF) . Алгоритмы и структуры данных: базовый набор инструментов . Спрингер.
^ Скиена, Стивен С. (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 , МР 1681014 .
^ Раман, Раджив (1996), «Очереди с приоритетами: маленькие, монотонные и трансдихотомические», Алгоритмы - ESA '96 (Барселона) , Конспекты лекций по информатике, том. 1136, Берлин: Springer, стр. 121–137, номер документа : 10.1007/3-540-61680-2_51 , ISBN. 978-3-540-61680-1 , МР 1469229 , S2CID 17004419 .

[mehlhorn-1] Перейти обратно: ^а ^б Мельхорн, Курт ; Сандерс, Питер (2008). «Приоритетные очереди» (PDF) . Алгоритмы и структуры данных: базовый набор инструментов . Спрингер.

[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 , МР 1681014 .

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

[1]

[2]

[3]

[4]