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

редактировать

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

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

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

Содержание

1 Операции
2 Реализация
- 2.1 Простые реализации
- 2.2 Обычная реализация
- 2.3 Специализированные кучи
- 2.4 Сводка времени выполнения
3 Эквивалентность очередей приоритетов и сортировка алгоритмы
- 3.1 Использование очереди приоритетов для сортировки
- 3.2 Использование алгоритма сортировки для создания очереди приоритетов
4 Библиотеки
5 Приложения
- 5.1 Управление пропускной способностью
- 5.2 Моделирование дискретных событий
- 5.3 Алгоритм Дейкстры
- 5.4 Кодирование Хаффмана
- 5.5 Алгоритмы поиска лучшего первого
- 5.6 Алгоритм триангуляции ROAM
- 5.7 Алгоритм Прима для минимального связующего дерева
6 Параллельная очередь приоритетов
- 6.1 Параллельный параллельный доступ
- 6.2 K-элементные операции
7 См. Также
8 Ссылки
9 Дополнительная литература
10 Внешние ссылки

Операции

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

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 (node)}

pull () {foreach node in list {ifhest.priority < node.priority{ highest = node } } list.remove(highest) return highest }

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

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

pull () {high = list.get_at_index (list. length-1) list.remove (высший) return высший}

Обычная реализация

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

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

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

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

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

Когда необходимы только insert, find-min и extract-min, а в случае целочисленных приоритетов, очередь корзины может быть построена как массив связанных списков C плюс указатель top, первоначально C. Вставка элемента с ключом k добавляет элемент к k-му и обновляет top ← min (top, k), оба в постоянное время. Extract-min удаляет и возвращает один элемент из списка с индексом top, затем увеличивает верхний, если необходимо, до тех пор, пока он снова не укажет на непустой список; в худшем случае это занимает O (C) времени. Эти очереди полезны для сортировки вершин графа по их степени.
A дерево ван Эмде Боаса поддерживает минимум, максимум, вставку, удаление, поиск, предшественник и преемник за время O (log log C), но имеет место для небольших очередей около O (2), где m - количество бит в значении приоритета. Пространство может быть значительно уменьшено с помощью хеширования.
Fusion tree by Fredman и Willard реализует минимальную операцию за время O (1) и время вставки и извлечения операций в $O (журнал ⁡ n / log ⁡ log ⁡ C) {\ displaystyle O (\ log n / \ log \ log C)}$ ${ \ Displaystyle О (\ журнал п / \ журнал \ журнал C)}$ времени. Однако автор заявляет, что «наши алгоритмы представляют только теоретический интерес; постоянные факторы, влияющие на время выполнения, исключают практичность».

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

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

Сводка времени выполнения

Вот временная сложность различных структур данных кучи. Имена функций предполагают минимальную кучу. Значение «O (f)» и «Θ (f)» см. В нотации Big O.

Operation	find-min	delete-min	вставить	кнопка уменьшения	meld
двоичный	Θ (1)	Θ (log n)	O (log n)	O (log n)	Θ (n)
Левый	Θ (1)	Θ (log n)	Θ (log n)	O (log n)	Θ (log n)
Биномиальный	Θ (1)	Θ (log n)	Θ(1)	Θ (log n)	O (log n)
Фибоначчи	Θ (1)	O (log n)	Θ (1)	Θ(1)	Θ (1)
Сопряжение	Θ (1)	O (log n)	Θ (1)	o (log n)	Θ (1)
Brodal	Θ (1)	O (журнал n)	Θ (1)	Θ (1)	Θ (1)
	Θ (1)	O (log n)	Θ (1)	Θ(1)	Θ (1)
Строгий Фибоначчи	Θ (1)	O (log n)	Θ (1)	Θ (1)	Θ (1)
2–3 куча	O (log n)	O (log n)	O (log n)	Θ (1)	?

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

Использование приоритета q ueue to sort

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

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

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

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

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

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

Библиотеки

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

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

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

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

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

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

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

каркас Apple Core Foundation содержит структуру CFBinaryHeap, которая реализует мин-куча.

Приложения

Управление полосой пропускания

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

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

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

Моделирование дискретных событий

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

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

алгоритм Дейкстры

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

Кодирование Хаффмана

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

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

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

Алгоритм триангуляции ROAM

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

Алгоритм Прима для минимального связующего дерева

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

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

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

Параллельный параллельный доступ

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

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

параллельный доступ к приоритетной очереди может быть реализован в модели PRAM с одновременным чтением и одновременной записью (CRCW). Далее очередь с приоритетом реализована как список пропусков . Кроме того, примитив атомарной синхронизации CAS используется для освобождения списка пропуска блокировки. Узлы списка пропусков состоят из уникального ключа, приоритета, массива из указателей для каждого уровня, на следующие узлы и метки удаления. Метка удаления отмечает, что узел собирается быть удаленным процессом. Это гарантирует, что другие процессы могут соответствующим образом отреагировать на удаление.

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

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

Операции с K-элементами

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

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

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

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

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

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

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

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

См. Также

Ссылки

Дополнительная литература

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

Внешние ссылки

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