Очередь с монотонным приоритетом - Monotone priority queue

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

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

Приложения

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

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

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

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

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

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

использованная литература

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

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

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

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

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

[1]

[2]

[3]

[4]