Очередь с монотонным приоритетом

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

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

Приложения [ править ]

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

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

Точно так же в алгоритмах линии развертки в вычислительной геометрии события, при которых линия развертки пересекает точку интереса, имеют приоритет по координате точки пересечения, и эти события извлекаются в монотонном порядке. Монотонный порядок извлечения также имеет место в версии « ветвь и граница» - « лучший первый» . ^[1]^:¹²⁸

Структуры данных [ править ]

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

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

Ссылки [ править ]

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

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

[2] Skiena, Стивен С. (1998), Алгоритм Руководство по проектированию , Springer, стр. 181, ISBN 978-0-387-94860-7 CS1 maint: обескураженный параметр ( ссылка ).

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

[4] Раман, Раджив (1996), «Приоритетные очереди: маленькие, монотонные и транс-дихотомические» (PDF) , Алгоритмы - ESA '96 (Барселона) , Лекционные заметки по компьютерным наукам, 1136 , Берлин: Springer, стр. 121–137 , DOI : 10.1007 / 3-540-61680-2_51 , МР 1469229 .

[1]