Приоритетная очередь

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

Хотя очереди с приоритетами часто реализуются с помощью куч , они концептуально отличаются от куч. Очередь с приоритетом - это такое понятие, как « список » или « карта »; так же, как список может быть реализован с помощью связанного списка или массива , очередь с приоритетом может быть реализована с помощью кучи или множества других методов, таких как неупорядоченный массив.

Операции [ править ]

Очередь с приоритетом должна как минимум поддерживать следующие операции:

is_empty : проверить, нет ли в очереди элементов.
insert_with_priority : добавить в очередь элемент с соответствующим приоритетом.
pull_highest_priority_element : удалить элемент из очереди с наивысшим приоритетом и вернуть его.
Это также известно как « pop_element (Off) », « get_maximum_element » или « get_front (most) _element ».
Некоторые соглашения меняют порядок приоритетов, считая более низкие значения более высоким приоритетом, поэтому это также может быть известно как « get_minimum_element », а в литературе часто упоминается как « get-min ».
Вместо этого это может быть указано как отдельные функции « peek_at_highest_priority_element » и « delete_element », которые могут быть объединены для создания « pull_highest_priority_element ».

Кроме того, очень часто реализуется функция peek (в этом контексте часто называемая find-max или find-min ), которая возвращает элемент с наивысшим приоритетом, но не изменяет очередь, и почти всегда выполняется за время O (1) . Эта операция и ее производительность O (1) имеют решающее значение для многих приложений очередей с приоритетом.

Более продвинутые реализации могут поддерживать более сложные операции, такие как pull_lowest_priority_element , проверка первых нескольких элементов с наивысшим или самым низким приоритетом, очистка очереди, очистка подмножеств очереди, выполнение пакетной вставки, объединение двух или более очередей в одну, увеличение приоритета любого элемента и т. д.

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

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

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

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

Реализация [ править ]

Наивные реализации [ править ]

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

Например, можно сохранить все элементы в несортированном списке ( время вставки O (1)). Всякий раз, когда запрашивается элемент с наивысшим приоритетом, ищите среди всех элементов элемент с наивысшим приоритетом. ( O ( n ) время вытягивания),

insert (node) { list.append (узел)}

pull () { узел foreach в списке { if high.priority <node.priority { самый высокий = узел } } list.remove (самый высокий) самый высокий возврат}

В другом случае можно сохранить все элементы в списке сортировки по приоритету ( время сортировки вставки O (n)), всякий раз, когда запрашивается элемент с наивысшим приоритетом, может быть возвращен первый в списке. ( O (1) время вытягивания)

insert (node) { foreach (индекс, элемент) в списке { if node.priority <element.priority { list.insert_at_index (узел, индекс) } }}

pull () { высший = list.get_at_index (list.length-1) list.remove (самый высокий) самый высокий возврат}

Обычная реализация [ править ]

Для повышения производительности очереди с приоритетами обычно основаны на куче , что дает производительность O (log n ) для вставок и удалений и O ( n ) для первоначального построения из набора из n элементов. Варианты базовой структуры данных кучи, такие как парные кучи или кучи Фибоначчи, могут обеспечить лучшие границы для некоторых операций. ^[1]

В качестве альтернативы, когда используется самобалансирующееся двоичное дерево поиска , вставка и удаление также занимают время O (log n ), хотя построение деревьев из существующих последовательностей элементов занимает время O ( n log n ); это типично, когда у кого-то уже может быть доступ к этим структурам данных, например, со сторонними или стандартными библиотеками.

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

Специализированные кучи [ править ]

Существует несколько специализированных структур данных кучи, которые либо предоставляют дополнительные операции, либо превосходят реализации на основе кучи для определенных типов ключей, в частности, для целочисленных ключей. Предположим, что набор возможных ключей равен {1, 2, ..., C}.

Когда только вставки , найти-мин и экстракт мин необходимы , и в случае целых приоритетов, очередь ковша может быть построена как массив $C$ связанных списки плюс указатель $вершину$ первоначально $C$ . Вставка элемента с ключом $k$ добавляет элемент к $k$ 'th и обновляет $top \leftarrow min (top, k)$ , оба в постоянное время. Extract-min удаляет и возвращает один элемент из списка с индексом $top$ , затем при необходимости увеличивает значение $top$ до тех пор, пока он снова не укажет на непустой список; это занимает $O (C)$ время в худшем случае. Эти очереди полезны для сортировки вершин графа по их степени. ^[2]^{: 374}
Ван Эмде Боас дерево поддерживает минимальные , максимальная , вставка , удаление , поиск , экстракт мин , экстракт-макс , предшественника и преемник операции в O (журнал журнал C ) время, но имеет стоимость пространства для небольших очередей около O ( 2 ^{m / 2} ), где m - количество бит в значении приоритета. ^[3] Пространство можно значительно уменьшить с помощью хеширования.
Дерево Сплав по Фредман и Willard реализует минимальная операция в O (1) времени и вставка и экстракт мин операции времени. Однако автор заявляет, что «Наши алгоритмы представляют только теоретический интерес; постоянные факторы, влияющие на время выполнения, исключают практичность». ^[4] ${\ Displaystyle О (\ журнал п / \ журнал \ журнал C)}$

Для приложений, которые выполняют множество операций « просмотра » для каждой операции «extract-min», временная сложность действий просмотра может быть уменьшена до O (1) во всех реализациях дерева и кучи путем кэширования элемента с наивысшим приоритетом после каждой вставки и удаления. Для вставки это добавляет не более постоянной стоимости, поскольку вновь вставленный элемент сравнивается только с ранее кэшированным минимальным элементом. Для удаления это не более чем добавляет дополнительные затраты на «просмотр», которые обычно дешевле, чем затраты на удаление, поэтому общая временная сложность существенно не изменяется.

Очереди с монотонным приоритетом - это специализированные очереди, оптимизированные для случая, когда никогда не вставляется ни один элемент с более низким приоритетом (в случае min-heap), чем любой ранее извлеченный элемент. Это ограничение встречается в нескольких практических приложениях приоритетных очередей.

Сводка времени работы [ править ]

Вот временные сложности ^[5] различных структур данных кучи. Имена функций предполагают минимальную кучу. Для значения " O ( F )" и " thetas ; ( е )" см Big O нотацию .

Операция	find-min	delete-min	вставлять	клавиша уменьшения	объединить
Двоичный ^[5]	Θ (1)	Θ (журнал n )	O (журнал n )	O (журнал n )	Θ ( п )
Левый	Θ (1)	Θ (журнал n )	Θ (журнал n )	O (журнал n )	Θ (журнал n )
Биномиальный ^[5]^[6]	Θ (1)	Θ (журнал n )	Θ (1) ^[а]	Θ (журнал n )	O (log n ) ^[b]
Фибоначчи ^[5]^[7]	Θ (1)	O (log n ) ^[a]	Θ (1)	Θ (1) ^[а]	Θ (1)
Сопряжение ^[8]	Θ (1)	O (log n ) ^[a]	Θ (1)	о (журнал п ) ^[а]^[с]	Θ (1)
Бродал ^[11]^[d]	Θ (1)	O (журнал n )	Θ (1)	Θ (1)	Θ (1)
Ранговые пары ^[13]	Θ (1)	O (log n ) ^[a]	Θ (1)	Θ (1) ^[а]	Θ (1)
Строгий Фибоначчи ^[14]	Θ (1)	O (журнал n )	Θ (1)	Θ (1)	Θ (1)
2–3 кучи ^[15]	O (журнал n )	O (log n ) ^[a]	O (log n ) ^[a]	Θ (1)	?

^ a b c d e f g h i Амортизированное время.
^ n - размер большей кучи.
^ Нижняя оценка^[9] верхняя оценка^[10] ${\ Displaystyle \ Omega (\ журнал \ журнал п),}$ ${\ displaystyle O (2 ^ {2 {\ sqrt {\ log \ log n}}}).}$
^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением ключа уменьшения, который не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). ^[12]

Эквивалентность приоритетных очередей и алгоритмов сортировки [ править ]

Использование приоритетной очереди для сортировки [ править ]

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

Имя	Реализация приоритетной очереди	Лучший	Средний	Наихудший
Heapsort	Куча	${\ Displaystyle п \ журнал (п)}$	${\ Displaystyle п \ журнал (п)}$	${\ Displaystyle п \ журнал (п)}$
Smoothsort	Леонардо Хип	${\ displaystyle n}$	${\ Displaystyle п \ журнал (п)}$	${\ Displaystyle п \ журнал (п)}$
Выборочная сортировка	Неупорядоченный массив	${\ Displaystyle п ^ {2}}$	${\ Displaystyle п ^ {2}}$	${\ Displaystyle п ^ {2}}$
Вставка сортировки	Упорядоченный массив	${\ displaystyle n}$	${\ Displaystyle п ^ {2}}$	${\ Displaystyle п ^ {2}}$
Сортировка дерева	Самобалансирующееся двоичное дерево поиска	${\ Displaystyle п \ журнал (п)}$	${\ Displaystyle п \ журнал (п)}$	${\ Displaystyle п \ журнал (п)}$

Использование алгоритма сортировки для создания очереди с приоритетом [ править ]

Алгоритм сортировки также может использоваться для реализации очереди приоритетов. В частности, Торуп говорит: ^[16]

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

То есть, если есть алгоритм сортировки , который может сортировать в O ( S ) время на ключ, где S является некоторой функцией от п и размера слова , ^[17] , то можно использовать данную процедуру для создания очереди приоритета , где тяговые элемент с наивысшим приоритетом - это время O (1), а вставка новых элементов (и удаление элементов) - время O ( S ). Например, если у кого-то есть алгоритм сортировки O ( n log n ), можно создать приоритетную очередь с O (1) извлечением и вставкой O (n log n ).

Библиотеки [ править ]

Очередь с приоритетом часто рассматривается как « структура данных контейнера ».

Standard Template Library (STL), и C ++ стандарт 1998, определяет в priority_queueкачестве одного из STL контейнеров адаптеров шаблонов классов . Однако он не указывает, как должны обслуживаться два элемента с одинаковым приоритетом, и действительно, общие реализации не будут возвращать их в соответствии с их порядком в очереди. Он реализует очередь с максимальным приоритетом и имеет три параметра: объект сравнения для сортировки, такой как объект функции (по умолчанию less <T>, если не указано), базовый контейнер для хранения структур данных (по умолчанию std :: vector <T>), и два итератора в начало и конец последовательности. В отличие от реальных контейнеров STL, он не допускает итерацийсвоих элементов (он строго придерживается своего абстрактного определения типа данных). В STL также есть служебные функции для управления другим контейнером с произвольным доступом в виде двоичной максимальной кучи. Библиотеки Boost также имеют реализацию в куче библиотек.

Модуль Python heapq реализует двоичную минимальную кучу поверх списка.

Библиотека Java содержит PriorityQueueкласс, который реализует очередь с минимальным приоритетом.

Библиотека Scala содержит класс PriorityQueue , который реализует очередь с максимальным приоритетом.

Библиотека Go содержит модуль контейнера / кучи , который реализует минимальную кучу поверх любой совместимой структуры данных.

Расширение стандартной библиотеки PHP содержит класс SplPriorityQueue .

Фреймворк Apple Core Foundation содержит структуру CFBinaryHeap , которая реализует min-heap.

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

Управление пропускной способностью [ править ]

Очередь с приоритетом может использоваться для управления ограниченными ресурсами, такими как пропускная способность линии передачи от сетевого маршрутизатора . В случае постановки в очередь исходящего трафика из-за недостаточной пропускной способности все другие очереди могут быть остановлены для отправки трафика из очереди с наивысшим приоритетом по прибытии. Это гарантирует, что приоритетный трафик (такой как трафик в реальном времени, например, поток RTP соединения VoIP ) пересылается с наименьшей задержкой и наименьшей вероятностью отклонения из-за того, что очередь достигает максимальной емкости. Весь другой трафик можно обрабатывать, когда очередь с наивысшим приоритетом пуста. Другой используемый подход - отправка непропорционально большего объема трафика из очередей с более высоким приоритетом.

Многие современные протоколы для локальных сетей также включают концепцию приоритетных очередей на подуровне управления доступом к среде (MAC), чтобы гарантировать, что высокоприоритетные приложения (такие как VoIP или IPTV ) имеют меньшую задержку, чем другие приложения, которые могут обслуживаться с лучший сервис. Примеры включают IEEE 802.11e (поправка к IEEE 802.11, которая обеспечивает качество обслуживания ) и ITU-T G.hn (стандарт для высокоскоростной локальной сети с использованием существующей домашней проводки ( линии электропередач , телефонные линии и коаксиальные кабели ).

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

Дискретное моделирование событий [ править ]

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

См. Также : Планирование (вычисления) , теория массового обслуживания

Алгоритм Дейкстры [ править ]

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

Кодирование Хаффмана [ править ]

Кодирование Хаффмана требует многократного получения двух самых низкочастотных деревьев. Очередь с приоритетом - один из способов сделать это .

Алгоритмы поиска лучшего первого [ править ]

Лучшие-первых поисковые алгоритмы, такие как A * алгоритм поиска , найти кратчайший путь между двумя вершинами или узлами одного взвешенного графа , пытаясь из наиболее перспективных маршрутов в первую очередь. Очередь с приоритетом (также известная как бахрома ) используется для отслеживания неисследованных маршрутов; тот, для которого оценка (нижняя граница в случае A *) общей длины пути является наименьшей, получает высший приоритет. Если ограничения памяти делают поиск лучшего первого непрактичным, вместо него можно использовать такие варианты, как алгоритм SMA * , с двусторонней приоритетной очередью, позволяющей удалять элементы с низким приоритетом.

Алгоритм триангуляции ROAM [ править ]

Алгоритм оптимальной адаптации сеток в реальном времени ( ROAM ) вычисляет динамически изменяющуюся триангуляцию местности. Он работает, разделяя треугольники там, где требуется больше деталей, и объединяя их там, где требуется меньше деталей. Алгоритм присваивает каждому треугольнику на местности приоритет, обычно связанный с уменьшением ошибки, если этот треугольник будет разделен. Алгоритм использует две очереди приоритета: одну для треугольников, которые можно разделить, а другую для треугольников, которые можно объединить. На каждом шаге треугольник из очереди разделения с наивысшим приоритетом разделяется, или треугольник из очереди слияния с самым низким приоритетом объединяется со своими соседями.

Алгоритм Прима для минимального остовного дерева [ править ]

Использование мин кучи очереди приоритета в алгоритме Прима найти минимального остовного дерева в виде подключенного и неориентированного графа , можно добиться хорошего времени работы. Эта очередь с приоритетом минимальной кучи использует структуру данных минимальной кучи, которая поддерживает такие операции, как вставка , минимум , извлечение-минимум , уменьшение-ключ . ^[18] В этой реализации вес ребер используется для определения приоритета вершин . Чем меньше вес, тем выше приоритет и выше вес, тем ниже приоритет. ^[19]

Очередь с параллельным приоритетом [ править ]

Распараллеливание может использоваться для ускорения очередей с приоритетом, но требует некоторых изменений в интерфейсе очереди с приоритетами. Причина таких изменений заключается в том, что последовательное обновление обычно требует только затрат или затрат, а распараллеливание такой операции не дает практического преимущества. Одно из возможных изменений - разрешить одновременный доступ нескольких процессоров к одной и той же приоритетной очереди. Второе возможное изменение - разрешить пакетные операции, которые работают с элементами, а не только с одним элементом. Например, extractMin удалит первые элементы с наивысшим приоритетом. ${\ textstyle O (1)}$ ${\ textstyle О (\ журнал п)}$ ${\ textstyle k}$ ${\ textstyle k}$

Параллельный параллельный доступ [ править ]

Если приоритетная очередь разрешает одновременный доступ, несколько процессов могут одновременно выполнять операции с этой приоритетной очередью. Однако здесь возникают две проблемы. Прежде всего, определение семантики отдельных операций больше не является очевидным. Например, если два процесса хотят извлечь элемент с наивысшим приоритетом, должны ли они получить один и тот же элемент или разные? Это ограничивает параллелизм на уровне программы, использующей очередь приоритетов. Кроме того, поскольку несколько процессов имеют доступ к одному и тому же элементу, это приводит к конфликту.

Узел 3 вставлен и устанавливает указатель узла 2 на узел 3. Сразу после этого узел 2 удаляется, а указатель узла 1 устанавливается на узел 4. Теперь узел 3 больше недоступен.

Параллельный доступ к приоритетной очереди может быть реализован в модели PRAM с одновременным чтением и одновременной записью (CRCW). В дальнейшем приоритетная очередь реализована как список пропуска . ^[20]^[21] Кроме того, для освобождения от блокировки списка пропусков используется примитив атомарной синхронизации, CAS . Узлы списка пропускаемого состоят из уникального ключа, в приоритетном порядке массива из указателей , для каждого уровня, в следующие узлы и удаление метки. В Удалять знак знаки , если узел собирается быть удален процессом. Это гарантирует, что другие процессы могут соответствующим образом отреагировать на удаление.

вставить (е): Сначала создается новый узел с ключом и приоритетом. Кроме того, узлу назначается ряд уровней, что диктует размер массива указателей. Затем выполняется поиск, чтобы найти правильную позицию, в которую нужно вставить новый узел. Поиск начинается с первого узла и с самого высокого уровня. Затем список пропуска перемещается вниз до самого нижнего уровня, пока не будет найдена правильная позиция. Во время поиска для каждого уровня последний пройденный узел будет сохранен как родительский узел для нового узла на этом уровне. Кроме того, узел, на который указывает указатель на этом уровне родительского узла, будет сохранен как узел-преемник нового узла на этом уровне. Впоследствии для каждого уровня нового узла указатели родительского узла будут установлены на новый узел. Наконец, указатели для каждого уровня,нового узла будут присвоены соответствующие узлы-преемники.
extract-min : Сначала просматривается список пропусков, пока не будет достигнут узел, метка удаления которого не установлена. Эта метка удаления для этого узла установлена в истинное значение. Наконец, обновляются указатели родительских узлов удаленного узла.

Если разрешен одновременный доступ к приоритетной очереди, между двумя процессами могут возникнуть конфликты. Например, конфликт возникает, если один процесс пытается вставить новый узел, но в то же время другой процесс собирается удалить предшественника этого узла. ^[20] Существует риск того, что новый узел будет добавлен в список пропуска, но недоступен. ( См. Изображение )

K-элементные операции [ править ]

В этом параметре операции с приоритетной очередью обобщены для пакета элементов. Например, k_extract-min удаляет самые маленькие элементы очереди приоритетов и возвращает их. ${\ textstyle k}$ ${\ textstyle k}$

В настройке с общей памятью параллельная очередь приоритетов может быть легко реализована с использованием параллельных двоичных деревьев поиска и древовидных алгоритмов на основе соединений . В частности, k_extract-min соответствует разбиению в двоичном дереве поиска, которое имеет стоимость и дает дерево, содержащее самые маленькие элементы. k_insert может применяться путем объединения исходной приоритетной очереди и пакета вставок. Если пакет уже отсортирован по ключу, k_insert имеет стоимость. В противном случае нам нужно сначала отсортировать партию, поэтому стоимость составит ${\ textstyle О (\ журнал п)}$ ${\ textstyle k}$ ${\ Displaystyle О (к \ журнал (1 + {\ гидроразрыва {п} {к}}))}$ ${\ Displaystyle О (к \ журнал (1 + {\ гидроразрыва {n} {k}}) + к \ журнал к) = О (к \ журнал п)}$ . Аналогично могут применяться и другие операции для очереди с приоритетом. Например, k_decrease-key можно выполнить, сначала применив разницу, а затем объединение , которое сначала удаляет элементы, а затем вставляет их обратно с обновленными ключами. Все эти операции в высшей степени параллельны, и их теоретическая и практическая эффективность можно найти в соответствующих исследовательских работах. ^[22]^[23]

В оставшейся части этого раздела обсуждается алгоритм распределенной памяти на основе очередей. Мы предполагаем, что каждый процессор имеет свою собственную локальную память и локальную (последовательную) очередь приоритетов. Элементы глобальной (параллельной) очереди приоритета распределяются по всем процессорам.

k_extract-min выполняется в приоритетной очереди с тремя процессорами. Зеленые элементы возвращаются и удаляются из очереди приоритетов.

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

Это свойство используется при выполнении k_extract-min , так как самые маленькие элементы каждой локальной очереди удаляются и собираются в результирующий набор. Элементы в наборе результатов по-прежнему связаны с их исходным процессором. Количество элементов , удаляемых из каждой локальной очереди, зависит от количества процессоров . ^[24] Путем параллельного отбора определяются самые маленькие элементы результирующего набора. С большой долей вероятности это самые маленькие элементы в мире. Если нет, элементы снова удаляются из каждой локальной очереди и помещаются в набор результатов. Это делается до тех пор, пока в результирующем наборе не появятся самые маленькие элементы. Теперь эти ${\ textstyle m}$ ${\ textstyle m}$ ${\ textstyle k}$ ${\ textstyle p}$ ${\ textstyle k}$ ${\ textstyle k}$ ${\ textstyle m}$ ${\ textstyle k}$ ${\ textstyle k}$ элементы могут быть возвращены. Все остальные элементы набора результатов вставляются обратно в свои локальные очереди. Время работы k_extract-мин , как ожидается , где и есть размер очереди приоритетов. ^[24] ${\textstyle O({\frac {k}{p}}log(n))}$ ${\textstyle k=\Omega (p\cdot log(p))}$ ${\textstyle n}$

Очередь с приоритетом может быть дополнительно улучшена, если не перемещать оставшиеся элементы набора результатов непосредственно обратно в локальные очереди после операции k_extract-min . Это позволяет избежать постоянного перемещения элементов между набором результатов и локальными очередями.

Удалив сразу несколько элементов, можно значительно ускорить работу. Но не все алгоритмы могут использовать такую приоритетную очередь. Например, алгоритм Дейкстры не может работать сразу на нескольких узлах. Алгоритм выбирает узел с наименьшим расстоянием от очереди приоритетов и вычисляет новые расстояния для всех его соседних узлов. Если вы удалите узлы, работа на одном узле может изменить расстояние до другого узла. Таким образом, использование операций с k-элементами разрушает свойство установки метки алгоритма Дейкстры. ${\textstyle k}$ ${\textstyle k}$

См. Также [ править ]

Пакетная очередь
Очередь команд
Планировщик заданий

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

^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «Глава 20: Кучи Фибоначчи». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 476–497. ISBN 0-262-03293-7.Третье издание, с. 518.
^ Skiena, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science + Business Media . ISBN 978-1-849-96720-4.
^ П. ван Эмде Боас. Сохранение порядка в лесу менее чем за логарифмическое время. В материалах 16-го ежегодного симпозиума по основам информатики , страницы 75-84. Компьютерное общество IEEE, 1975.
^ Майкл Л. Фредман и Дэн Э. Уиллард. Превышение теоретической информационной границы с помощью деревьев слияния. Журнал компьютерных и системных наук , 48 (3): 533-551, 1994.
^ a b c d Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
^ "Биномиальная куча | Блестящая математика и наука вики" . brilliant.org . Проверено 30 сентября 2019 .
^ Фредман, Майкл Лоуренс ; Тарджан, Роберт Э. (июль 1987 г.). «Куча Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . DOI : 10.1145 / 28869.28874 .
^ Яконо, Джон (2000), "Улучшенные верхние границы для парных куч", Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Lecture Notes in Computer Science, 1851 , Springer-Verlag, стр. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007 / 3-540-44985-X_5 , ISBN 3-540-67690-2
^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. DOI : 10.1145 / 320211.320214 .
^ Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. С. 174–183. CiteSeerX 10.1.1.549.471 . DOI : 10.1109 / SFCS.2005.75 . ISBN 0-7695-2468-0.
^ Бродал, Герт С. (1996), "Эффективные приоритетные очереди наихудшего случая" (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
^ Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Строительство кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). С. 338–341. ISBN 0-471-46983-1.
^ Haeupler, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). "Куча ранговых пар" (PDF) . SIAM J. Computing . 40 (6): 1463–1485. DOI : 10.1137 / 100785351 .
^ Бродал, Герт Стёльтинг ; Лагогианнис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. С. 1177–1184. CiteSeerX 10.1.1.233.1740 . DOI : 10.1145 / 2213977.2214082 . ISBN 978-1-4503-1245-5.
^ Такаок, Тадао (1999), Теория 2-3 куч (PDF) , стр. 12
^ Thorup, Миккель (2007). «Равнозначность приоритетных очередей и сортировки». Журнал ACM . 54 (6): 28. DOI : 10,1145 / 1314690,1314692 . S2CID 11494634 .
^ «Архивная копия» (PDF) . Архивировано (PDF) из оригинала 20.07.2011 . Проверено 10 февраля 2011 . CS1 maint: archived copy as title (link)
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.
^ «Алгоритм Прима» . Компьютерщик для компьютерных фанатов. Архивировано 9 сентября 2014 года . Проверено 12 сентября 2014 года .
^ a b Сунделл, Хокан; Цигас, Филиппы (2005). «Быстрые очереди одновременных приоритетов без блокировок для многопоточных систем» . Журнал параллельных и распределенных вычислений . 65 (5): 609–627. DOI : 10.1109 / IPDPS.2003.1213189 . S2CID 20995116 .
^ Линден, Йонссон (2013), «Очередь одновременных приоритетов на основе Skiplist с минимальным количеством конфликтов памяти» , Технический отчет 2018-003 (на немецком языке)
^ Blelloch, Guy E .; Феризович, Даниэль; Sun, Yihan (2016), «Просто присоединитесь к параллельным упорядоченным множествам», симпозиум по параллельным алгоритмам и архитектурам, Proc. 28-го симпозиума ACM. Параллельные алгоритмы и архитектуры (SPAA 2016) , ACM, стр. 253–264, arXiv : 1602.02120 , doi : 10.1145 / 2935764.2935768 , ISBN 978-1-4503-4210-0, S2CID 2897793
^ Blelloch, Guy E .; Феризович, Даниэль; Sun, Yihan (2018), «PAM: параллельные расширенные карты», Труды 23-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования , ACM, стр. 290–304
^ a b Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных - базовый набор инструментов . Издательство Springer International. С. 226–229. DOI : 10.1007 / 978-3-030-25209-0 . ISBN 978-3-030-25208-3. S2CID 201692657 .

Дальнейшее чтение [ править ]

Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «Раздел 6.5: Приоритетные очереди». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 138–142. ISBN 0-262-03293-7.

Внешние ссылки [ править ]

Справочник по C ++ для std::priority_queue
Описания по Ли Killough
PQlib - библиотека очереди приоритетов с открытым исходным кодом для C
libpqueue - это общая реализация приоритетной очереди (кучи) (на языке C), используемая проектом HTTP-сервера Apache.
Обзор известных структур приоритетных очередей, сделанный Стефаном Ксеносом
Калифорнийский университет в Беркли - Компьютерные науки 61B - Лекция 24: Приоритетные очереди (видео) - Введение в приоритетные очереди с использованием двоичной кучи

[amortized-7] ^ a b c d e f g h i Амортизированное время.

[meld-8] - размер большей кучи.

[pairingdecreasekey-13] Нижняя оценка^[9] верхняя оценка^[10] ${\ Displaystyle \ Omega (\ журнал \ журнал п),}$ ${\ displaystyle O (2 ^ {2 {\ sqrt {\ log \ log n}}}).}$

[brodal-16] Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением ключа уменьшения, который не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). ^[12]

[CLRS_priority_queue_pp476-1] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «Глава 20: Кучи Фибоначчи». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 476–497. ISBN 0-262-03293-7.Третье издание, с. 518.

[2] Skiena, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science + Business Media . ISBN 978-1-849-96720-4.

[3] П. ван Эмде Боас. Сохранение порядка в лесу менее чем за логарифмическое время. В материалах 16-го ежегодного симпозиума по основам информатики , страницы 75-84. Компьютерное общество IEEE, 1975.

[4] Майкл Л. Фредман и Дэн Э. Уиллард. Превышение теоретической информационной границы с помощью деревьев слияния. Журнал компьютерных и системных наук , 48 (3): 533-551, 1994.

[CLRS-5] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.

[6] "Биномиальная куча | Блестящая математика и наука вики" . brilliant.org . Проверено 30 сентября 2019 .

[Fredman_And_Tarjan-9] Фредман, Майкл Лоуренс ; Тарджан, Роберт Э. (июль 1987 г.). «Куча Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . DOI : 10.1145 / 28869.28874 .

[Iacono-10] Яконо, Джон (2000), "Улучшенные верхние границы для парных куч", Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Lecture Notes in Computer Science, 1851 , Springer-Verlag, стр. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007 / 3-540-44985-X_5 , ISBN 3-540-67690-2

[Fredman1999-11] Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. DOI : 10.1145 / 320211.320214 .

[12] Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. С. 174–183. CiteSeerX 10.1.1.549.471 . DOI : 10.1109 / SFCS.2005.75 . ISBN 0-7695-2468-0.

[14] Бродал, Герт С. (1996), "Эффективные приоритетные очереди наихудшего случая" (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.

[15] Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Строительство кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). С. 338–341. ISBN 0-471-46983-1.

[17] Haeupler, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). "Куча ранговых пар" (PDF) . SIAM J. Computing . 40 (6): 1463–1485. DOI : 10.1137 / 100785351 .

[18] Бродал, Герт Стёльтинг ; Лагогианнис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. С. 1177–1184. CiteSeerX 10.1.1.233.1740 . DOI : 10.1145 / 2213977.2214082 . ISBN 978-1-4503-1245-5.

[19] Такаок, Тадао (1999), Теория 2-3 куч (PDF) , стр. 12

[20] Thorup, Миккель (2007). «Равнозначность приоритетных очередей и сортировки». Журнал ACM . 54 (6): 28. DOI : 10,1145 / 1314690,1314692 . S2CID 11494634 .

[21] «Архивная копия» (PDF) . Архивировано (PDF) из оригинала 20.07.2011 . Проверено 10 февраля 2011 . CS1 maint: archived copy as title (link)

[CLR-22] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.

[GEEKS-23] «Алгоритм Прима» . Компьютерщик для компьютерных фанатов. Архивировано 9 сентября 2014 года . Проверено 12 сентября 2014 года .

[skiplist-24] Сунделл, Хокан; Цигас, Филиппы (2005). «Быстрые очереди одновременных приоритетов без блокировок для многопоточных систем» . Журнал параллельных и распределенных вычислений . 65 (5): 609–627. DOI : 10.1109 / IPDPS.2003.1213189 . S2CID 20995116 .

[25] Линден, Йонссон (2013), «Очередь одновременных приоритетов на основе Skiplist с минимальным количеством конфликтов памяти» , Технический отчет 2018-003 (на немецком языке)

[join-based-26] Blelloch, Guy E .; Феризович, Даниэль; Sun, Yihan (2016), «Просто присоединитесь к параллельным упорядоченным множествам», симпозиум по параллельным алгоритмам и архитектурам, Proc. 28-го симпозиума ACM. Параллельные алгоритмы и архитектуры (SPAA 2016) , ACM, стр. 253–264, arXiv : 1602.02120 , doi : 10.1145 / 2935764.2935768 , ISBN 978-1-4503-4210-0, S2CID 2897793

[pam-27] Blelloch, Guy E .; Феризович, Даниэль; Sun, Yihan (2018), «PAM: параллельные расширенные карты», Труды 23-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования , ACM, стр. 290–304

[AlgToolbox-28] Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных - базовый набор инструментов . Издательство Springer International. С. 226–229. DOI : 10.1007 / 978-3-030-25209-0 . ISBN 978-3-030-25208-3. S2CID 201692657 .

vтеСтруктуры данных
Типы	Коллекция Контейнер
Абстрактный	Ассоциативный массив Multimap Список Куча Очередь Двусторонняя очередь Приоритетная очередь Двусторонняя приоритетная очередь Набор Multiset Непересекающееся множество
Массивы	Битовый массив Круглый буфер Динамический массив Хеш-таблица Дерево хешированных массивов Разреженная матрица
Связано	Список ассоциаций Связанный список Пропустить список Развернутый связанный список Связанный список XOR
Деревья	B-дерево Дерево двоичного поиска Дерево AA AVL дерево Красно-черное дерево Самобалансирующееся дерево Splay tree Куча Двоичная куча Биномиальная куча Куча Фибоначчи R-дерево R * дерево R + дерево R-дерево Гильберта Trie Хеш-дерево
Графики	Диаграмма двоичного решения Направленный ациклический граф Направленный ациклический граф слов
Список структур данных