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

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

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

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

Операции

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

• 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 ) время вытягивания),

вставить (узел){ list.append(узел)}

тянуть (){ самый высокий = list.get_first_element() foreach узел в списке { если наивысший.приоритет < node.priority { самый высокий = узел } } list.remove(самый высокий) возврат самый высокий}

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

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

тянуть (){ самый высокий = 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}.

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

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

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

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

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

1. Амортизированное время.
2. объединения в наихудшем случае до Θ (1); этот метод применим к любой структуре данных кучи, которая имеет вставку в Θ (1) и find-min , delete-min , объединение в O (log  n ).
3. Нижняя граница ^[9] верхняя граница ^[10] ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
4. Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). ^[15]

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

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

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

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

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

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

То есть, если существует алгоритм сортировки, который может сортировать за время O ( S ) на ключ, где S — некоторая функция от n и размера слова , ^[18] тогда можно использовать данную процедуру для создания приоритетной очереди, в которой вытягивание элемент с наивысшим приоритетом занимает время 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 реализует двоичную минимальную кучу поверх списка.

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

Библиотека .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 ) вычисляет динамически изменяющуюся триангуляцию ландшафта. Он работает путем разделения треугольников там, где требуется больше деталей, и объединения их там, где требуется меньше деталей. Алгоритм назначает каждому треугольнику на местности приоритет, обычно связанный с уменьшением ошибки, если этот треугольник будет разделен. Алгоритм использует две очереди приоритетов: одну для треугольников, которые можно разделить, и другую для треугольников, которые можно объединить. На каждом шаге треугольник из разделенной очереди с наивысшим приоритетом разделяется или треугольник из очереди слияния с наименьшим приоритетом объединяется со своими соседями.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «Глава 20: Кучи Фибоначчи». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 476–497. ISBN 0-262-03293-7.Третье издание, с. 518.
2. Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science+Business Media . ISBN 978-1-849-96720-4.
3. П. ван Эмде Боас. Поддержание порядка в лесу менее чем за логарифмическое время. В материалах 16-го ежегодного симпозиума по основам информатики , страницы 75-84. Компьютерное общество IEEE, 1975.
4. Майкл Л. Фредман и Дэн Э. Уиллард. Преодоление теории информации, связанной с деревьями слияния. Журнал компьютерных и системных наук , 48(3):533-551, 1994 г.
5. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
6. "Биномиальная куча | Блестящая вики по математике и естественным наукам" . блестящий.орг . Проверено 30 сентября 2019 г.
7. Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
8. Яконо, Джон (2000), «Улучшенные верхние границы для парных куч», Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Конспекты лекций по информатике, том. 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
9. Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214.
10. Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX 10.1.1.549.471 . дои : 10.1109/SFCS.2005.75. ISBN  0-7695-2468-0.
11. Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351.
12. Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . дои : 10.1145/28869.28874. 
13. Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . дои : 10.1145/2213977.2214082. ISBN  978-1-4503-1245-5.
14. Бродал, Герт С. (1996), «Эффективные приоритетные очереди в наихудшем случае» (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
15. Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Построение кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). стр. 338–341. ISBN 0-471-46983-1.
16. Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12
17. Торуп, Миккель (2007). «Эквивалентность приоритетных очередей и сортировки». Журнал АКМ . 54 (6): 28. дои : 10.1145/1314690.1314692. S2CID  11494634.
18. «Архивная копия» (PDF) . Архивировано (PDF) из оригинала 20 июля 2011 г. Проверено 10 февраля 2011 г.{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
19. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. п. 634. ИСБН 0-262-03384-4.«Чтобы эффективно реализовать алгоритм Прима, нам нужен быстрый способ выбора нового ребра для добавления в дерево, образованное ребрами в A».
20. «Алгоритм Прима». Выродок для гиков. 18 ноября 2012 года. Архивировано из оригинала 9 сентября 2014 года . Проверено 12 сентября 2014 г.
21. Санделл, Хокан; Цигас, Филиппас (2005). «Быстрые и одновременные очереди приоритетов без блокировки для многопоточных систем». Журнал параллельных и распределенных вычислений . 65 (5): 609–627. CiteSeerX 10.1.1.67.1310 . дои : 10.1109/IPDPS.2003.1213189. S2CID  20995116. 
22. Линден, Йонссон (2013), «Очередь с параллельным приоритетом на основе списков пропусков и минимальным конфликтом памяти», Технический отчет 2018-003 (на немецком языке)
23. Блеллох, Гай Э.; Феризович, Дэниел; Сунь, Ихан (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
24. Блеллох, Гай Э.; Феризович, Дэниел; Сунь, Ихан (2018), «PAM: параллельные дополненные карты», Материалы 23-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования , ACM, стр. 290–304
25. Сандерс, Питер; Мельхорн, Курт; Дитцфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных — базовый набор инструментов . Международное издательство Спрингер. стр. 226–229. дои : 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
• Описания Ли Киллоу
• libpqueue — это общая реализация очереди приоритетов (кучи) (на C), используемая проектом HTTP-сервера Apache.
• Обзор известных структур очередей с приоритетами, проведенный Стефаном Ксеносом.
• Калифорнийский университет в Беркли - Информатика 61B - Лекция 24: Очереди приоритетов (видео) - введение в очереди приоритетов с использованием двоичной кучи