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

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

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

Операции

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

• 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 ».

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

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

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

Выполнение

Наивные реализации

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

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

insert(node)
{
    list.append(node)
}

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

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

insert(node)
{
    foreach (index, element) in list
    {
        if node.priority < element.priority
        {
            list.insert_at_index(node,index)
            break
        }
    }
}

pull()
{
    highest = list.get_at_index(list.length-1)
    list.remove(highest)
    return highest
}

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

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

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

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

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

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

• только команды Insert , find-min и Extract-min Когда необходимы и в случае целочисленных приоритетов, очередь сегментов может быть построена как массив C связанных списков плюс указатель top первоначально C. , Вставка элемента с ключом k добавляет элемент в k -й список и обновляет top ← min(top, k ) , оба за постоянное время. Extract-min удаляет и возвращает один элемент из списка с индексом top , затем при необходимости увеличивает top, пока он снова не укажет на непустой список; это занимает время O ( C ) в худшем случае . Эти очереди полезны для сортировки вершин графа по их степени.
• Дерево Ван Эмде Боаса поддерживает операции минимума , максимума , вставки , удаления , поиска , извлечения-мин , извлечения-максимума , предшественника и преемника] за время O (log log C ), но для небольших очередей требуется пространство около O. (2 ^{м /2} ), где m — количество битов в значении приоритета. Пространство можно значительно уменьшить с помощью хеширования.
• Дерево Fusion Фредмана извлечения и Уилларда реализует минимальную операцию за время O (1), а вставки и - за минимальное время . операции $O(\log n/\log \log C)$время. Однако автор заявляет, что «Наши алгоритмы представляют только теоретический интерес; постоянные факторы, влияющие на время выполнения, исключают практичность».

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

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

Сводка времени работы

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

Операция	найти-мин	удаление-мин	клавиша уменьшения	вставлять	сливаться	помойка
Двоичный	я (1)	Θ (логарифм n )	Θ (логарифм n )	Θ (логарифм n )	Θ ( н )	Θ ( н )
Перекос	я (1)	О (log n ) утра.	О (log n ) утра.	О (log n ) утра.	О (log n ) утра.	Θ ( н ) утра.
Левый	я (1)	Θ (логарифм n )	Θ (логарифм n )	Θ (логарифм n )	Θ (логарифм n )	Θ ( н )
Биномиальный	я (1)	Θ (логарифм n )	Θ (логарифм n )	Θ (1) утра.	Θ (логарифм n )	Θ ( н )
Наклонный бином	я (1)	Θ (логарифм n )	Θ (логарифм n )	я (1)	Θ (логарифм n )	Θ ( н )
2–3 кучи	я (1)	О (log n ) утра.	я (1)	Θ (1) утра.	О ( войти )	Θ ( н )
Перекос снизу вверх	я (1)	О (log n ) утра.	О (log n ) утра.	Θ (1) утра.	Θ (1) утра.	Θ ( н ) утра.
Сопряжение	я (1)	О (log n ) утра.	о (log n ) утра.	я (1)	я (1)	Θ ( н )
Сопряжение по рангам	я (1)	О (log n ) утра.	Θ (1) утра.	я (1)	я (1)	Θ ( н )
Фибоначчи	я (1)	О (log n ) утра.	Θ (1) утра.	я (1)	я (1)	Θ ( н )
Строгий Фибоначчи	я (1)	Θ (логарифм n )	я (1)	я (1)	я (1)	Θ ( н )
Мостовая долина	я (1)	Θ (логарифм n )	я (1)	я (1)	я (1)	Θ ( н )

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

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

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

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

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

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

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

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

Библиотеки

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

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

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

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

.NET Библиотека содержит класс 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 Callmanager , который можно запрограммировать на запрет вызовов, которые превышают запрограммированный предел пропускной способности.

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

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

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

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

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

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

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

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

Алгоритмы поиска по принципу «лучший первый»

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

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

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

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

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

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

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

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

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

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

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

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

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

K -элементные операции

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

В условиях общей памяти параллельная очередь приоритетов может быть легко реализована с использованием параллельных деревьев двоичного поиска и алгоритмов деревьев на основе соединений . В частности, k_extract-min соответствует разбиению двоичного дерева поиска, которое имеет ${\textstyle O(\log n)}$ стоимость и дает дерево, содержащее ${\textstyle k}$ мельчайшие элементы. k_insert может применяться путем объединения исходной приоритетной очереди и пакета вставок. Если пакет уже отсортирован по ключу, k_insert имеет ${\textstyle O(k\log(1+{\frac {n}{k}}))}$ расходы. В противном случае нам нужно сначала отсортировать партию, поэтому стоимость будет равна ${\textstyle 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 как наименьшее ${\textstyle m}$ элементы каждой локальной очереди удаляются и собираются в набор результатов. Элементы результирующего набора по-прежнему связаны со своим исходным процессором. Количество элементов ${\textstyle m}$ который удаляется из каждой локальной очереди, зависит от ${\textstyle k}$ и количество процессоров ${\textstyle p}$. Путем параллельного выбора ${\textstyle k}$ определяются наименьшие элементы результирующего набора. С высокой вероятностью это глобальные ${\textstyle k}$ мельчайшие элементы. Если не, ${\textstyle m}$ элементы снова удаляются из каждой локальной очереди и помещаются в набор результатов. Это делается до тех пор, пока глобальный ${\textstyle k}$ наименьшие элементы находятся в наборе результатов. Теперь эти ${\textstyle k}$ элементы можно вернуть. Все остальные элементы набора результатов вставляются обратно в свои локальные очереди. время работы k_extract-min. Ожидается ${\textstyle O({\frac {k}{p}}\log(n))}$, где ${\textstyle k=\Omega (p\cdot \log(p))}$ и ${\textstyle n}$ — размер приоритетной очереди.

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

Удалив сразу несколько элементов, можно добиться значительного ускорения. Но не все алгоритмы могут использовать такую ​​очередь с приоритетами. Например, алгоритм Дейкстры не может работать на нескольких узлах одновременно. Алгоритм берет узел с наименьшим расстоянием из приоритетной очереди и вычисляет новые расстояния для всех соседних узлов. Если бы ты вынул ${\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
• Описания Ли Киллоу
• libpqueue — это общая реализация очереди приоритетов (кучи) (на C), используемая проектом HTTP-сервера Apache.
• Обзор известных структур очередей с приоритетами, проведенный Стефаном Ксеносом.
• Калифорнийский университет в Беркли - Информатика 61B - Лекция 24: Очереди приоритетов (видео) - введение в очереди приоритетов с использованием двоичной кучи