Очередь с приоритетом: абстрактный тип данных и реализации

Введение

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

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

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

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

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

Существует несколько специализированных структур данных кучи, которые либо предоставляют дополнительные операции, либо превосходят реализации на основе кучи для конкретных типов ключей, особенно для целых ключей. Предположим, что множество возможных ключей – {1, 2, ..., C}. Когда требуются только операции вставки, поиска минимума и извлечения минимума, а приоритеты являются целыми числами, можно построить очередь ковшом (bucket queue) в виде массива из C связных списков и указателя `top`, изначально равного C. Вставка элемента с ключом k добавляет этот элемент в k-й список и обновляет `top` до min(`top`, k), обе эти операции выполняются за константное время. Операция `extract min` удаляет и возвращает один элемент из списка с индексом `top`, затем, при необходимости, увеличивает `top` до тех пор, пока он не укажет на непустой список; в худшем случае это занимает O(C) времени. Такие очереди полезны для сортировки вершин графа по их степени. Дерево ван Эмде Боаса поддерживает операции поиска минимума, максимума, вставки, удаления, поиска, извлечения минимума, извлечения максимума, поиска предшественника и преемника за время O(log log C), но требует затрат памяти для небольших очередей порядка O(2<sup>m/2</sup>), где m – количество бит в значении приоритета. Объем используемой памяти можно существенно уменьшить с помощью хеширования. Дерево Fusion, разработанное Фредманом и Уиллардом, реализует операцию поиска минимума за время O(1), а операции вставки и извлечения минимума – за время. Однако, по словам авторов, "наши алгоритмы представляют лишь теоретический интерес; константные факторы, влияющие на время выполнения, делают их непрактичными". Для приложений, выполняющих много операций "peek" на каждую операцию "extract min", временную сложность операций peek можно снизить до O(1) во всех реализациях деревьев и куч, кэшируя элемент с наивысшим приоритетом после каждой вставки и удаления. Для вставки это добавляет не более чем константные затраты, поскольку вновь вставленный элемент сравнивается только с ранее закэшированным минимальным элементом. Для удаления это добавляет не более чем дополнительную стоимость операции "peek", которая обычно дешевле стоимости удаления, поэтому общая временная сложность существенно не изменяется. Монотонные очереди приоритета – это специализированные очереди, оптимизированные для случая, когда ни один вставляемый элемент не имеет приоритет ниже (в случае min-кучи), чем любой ранее извлеченный элемент. Это ограничение выполняется в нескольких практических приложениях очередей приоритета.

There are several specialized heap data structures that either supply additional operations or outperform heap based implementations for specific types of keys, specifically integer keys. Suppose the set of possible keys is {1, 2, , C}. When only insert, find min and extract min are needed and in case of integer priorities, a bucket queue can be constructed as an array of C linked lists plus a pointer top, initially C. Inserting an item with key k appends the item to the k'th list, and updates top ← min(top, k), both in constant time. Extract min deletes and returns one item from the list with index top, then increments top if needed until it again points to a non empty list; this takes O(C) time in the worst case. These queues are useful for sorting the vertices of a graph by their degree. A van Emde Boas tree supports the minimum, maximum, insert, delete, search, extract min, extract max, predecessor and successor] operations in O(log log C) time, but has a space cost for small queues of about O(2m/2), where m is the number of bits in the priority value. The space can be reduced significantly with hashing. The Fusion tree by Fredman and Willard implements the minimum operation in O(1) time and insert and extract min operations in time. However it is stated by the author that, "Our algorithms have theoretical interest only; The constant factors involved in the execution times preclude practicality." For applications that do many "peek" operations for every "extract min" operation, the time complexity for peek actions can be reduced to O(1) in all tree and heap implementations by caching the highest priority element after every insertion and removal. For insertion, this adds at most a constant cost, since the newly inserted element is compared only to the previously cached minimum element. For deletion, this at most adds an additional "peek" cost, which is typically cheaper than the deletion cost, so overall time complexity is not significantly impacted. Monotone priority queues are specialized queues that are optimized for the case where no item is ever inserted that has a lower priority (in the case of min heap) than any item previously extracted. This restriction is met by several practical applications of priority queues.

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

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

Мы представляем общее детерминированное линейное по пространству сведение задачи приоритетных очередей к задаче сортировки, подразумевающее, что если мы можем сортировать до 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 также содержат реализацию в библиотеке `heap`. Модуль `heapq` в Python реализует бинарную кучу минимума на основе списка. Библиотека Java содержит класс, реализующий очередь с минимальным приоритетом в виде бинарной кучи. Библиотека .NET содержит класс `PriorityQueue`, реализующий кучу минимума, основанную на массиве, с четверичным деревом. Библиотека Scala содержит класс `PriorityQueue`, реализующий очередь с максимальным приоритетом. Библиотека Go содержит модуль `container/heap`, реализующий кучу минимума на основе любой совместимой структуры данных. Расширение Standard PHP Library содержит класс `SplPriorityQueue`. Фреймворк Core Foundation от Apple содержит структуру `CFBinaryHeap`, реализующую кучу минимума.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если очередь приоритетов допускает одновременный доступ, несколько процессов могут одновременно выполнять операции над этой очередью приоритетов. Однако это порождает две проблемы. Во-первых, определение семантики отдельных операций становится неочевидным. Например, если два процесса хотят извлечь элемент с наивысшим приоритетом, должны ли они получить один и тот же элемент или разные? Это ограничивает параллелизм на уровне программы, использующей очередь приоритетов. Кроме того, поскольку несколько процессов имеют доступ к одному и тому же элементу, это приводит к конкуренции. Одновременный доступ к очереди приоритетов может быть реализован на модели PRAM с одновременным чтением и одновременной записью (CRCW). Далее очередь приоритетов реализована в виде списка пропусков. Для обеспечения отсутствия блокировок в списке пропусков используется атомарный примитив синхронизации CAS. Узлы списка пропусков состоят из уникального ключа, приоритета, массива указателей для каждого уровня на следующие узлы и метки удаления. Метка удаления указывает, что узел собирается быть удален процессом. Это гарантирует, что другие процессы смогут соответствующим образом отреагировать на удаление. insert(e): Сначала создается новый узел с ключом и приоритетом. Кроме того, узлу присваивается количество уровней, которое определяет размер массива указателей. Затем выполняется поиск для определения правильной позиции для вставки нового узла. Поиск начинается с первого узла и с верхнего уровня. Затем список пропусков просматривается вниз до нижнего уровня, пока не будет найдена правильная позиция. В процессе поиска для каждого уровня последний пройденный узел сохраняется как родительский узел для нового узла на этом уровне. Кроме того, узел, на который указывает указатель родительского узла на этом уровне, сохраняется как узел-преемник нового узла на этом уровне. Затем для каждого уровня нового узла указатели родительского узла устанавливаются на новый узел. Наконец, указатели для каждого уровня нового узла устанавливаются на соответствующие узлы-преемники. extract min: Сначала список пропусков просматривается до тех пор, пока не будет достигнут узел, у которого не установлена метка удаления. Затем эта метка удаления устанавливается в true для этого узла. Наконец, указатели родительских узлов удаленного узла обновляются. Если допускается одновременный доступ к очереди приоритетов, между двумя процессами могут возникнуть конфликты. Например, конфликт возникает, если один процесс пытается вставить новый узел, а в то же время другой процесс собирается удалить предшественника этого узла. Остальная часть этого раздела посвящена алгоритму на основе очереди, реализованному в распределенной памяти. Предполагается, что каждый процессор имеет свою локальную память и локальную (последовательную) очередь приоритетов. Элементы глобальной (параллельной) очереди приоритетов распределены между всеми процессорами. Операция k insert равномерно случайным образом назначает элементы процессорам, которые вставляют элементы в свои локальные очереди. Следует отметить, что отдельные элементы все еще могут быть вставлены в очередь. Используя эту стратегию, глобальные наименьшие элементы с высокой вероятностью находятся в объединении локальных наименьших элементов каждого процессора. Таким образом, каждый процессор содержит представительную часть глобальной очереди приоритетов. Это свойство используется при выполнении k extract min, поскольку наименьшие элементы каждой локальной очереди удаляются и собираются в результирующий набор. Элементы в результирующем наборе по-прежнему связаны с их исходным процессором. Количество элементов, удаляемых из каждой локальной очереди, зависит от k и количества процессоров. С помощью параллельного отбора определяются k наименьших элементов результирующего набора. С высокой вероятностью это глобальные k наименьших элементов. Если это не так, k элементов снова удаляются из каждой локальной очереди и помещаются в результирующий набор. Это повторяется до тех пор, пока в результирующем наборе не окажутся глобальные k наименьших элементов. Теперь эти k элементов могут быть возвращены. Все остальные элементы результирующего набора вставляются обратно в свои локальные очереди. Ожидаемое время выполнения k extract min равно , где и – размер очереди приоритетов. Приоритетную очередь можно дополнительно улучшить, не перемещая оставшиеся элементы результирующего набора непосредственно обратно в локальные очереди после операции k extract min. Это позволяет избежать постоянного перемещения элементов между результирующим набором и локальными очередями. Удаляя несколько элементов одновременно, можно добиться значительного ускорения. Однако не все алгоритмы могут использовать такой тип очереди приоритетов. Например, алгоритм Дейкстры не может работать с несколькими узлами одновременно. Алгоритм извлекает из очереди приоритетов узел с наименьшим расстоянием и вычисляет новые расстояния для всех его соседних узлов. Если извлечь k узлов, работа с одним узлом может изменить расстояние другого узла из этих k узлов. Таким образом, использование k-элементных операций нарушает свойство установки меток алгоритма Дейкстры.

If the priority queue allows concurrent access, multiple processes can perform operations concurrently on that priority queue. However, this raises two issues. First of all, the definition of the semantics of the individual operations is no longer obvious. For example, if two processes want to extract the element with the highest priority, should they get the same element or different ones? This restricts parallelism on the level of the program using the priority queue. In addition, because multiple processes have access to the same element, this leads to contention. The concurrent access to a priority queue can be implemented on a Concurrent Read, Concurrent Write (CRCW) PRAM model. In the following the priority queue is implemented as a skip list. In addition, an atomic synchronization primitive, CAS, is used to make the skip list lock free. The nodes of the skip list consists of a unique key, a priority, an array of pointers, for each level, to the next nodes and a delete mark. The delete mark marks if the node is about to be deleted by a process. This ensures that other processes can react to the deletion appropriately. insert(e): First, a new node with a key and a priority is created. In addition, the node is assigned a number of levels, which dictates the size of the array of pointers. Then a search is performed to find the correct position where to insert the new node. The search starts from the first node and from the highest level. Then the skip list is traversed down to the lowest level until the correct position is found. During the search, for every level the last traversed node will be saved as parent node for the new node at that level. In addition, the node to which the pointer, at that level, of the parent node points towards, will be saved as the successor node of the new node at that level. Afterwards, for every level of the new node, the pointers of the parent node will be set to the new node. Finally, the pointers, for every level, of the new node will be set to the corresponding successor nodes. extract min: First, the skip list is traversed until a node is reached whose delete mark is not set. This delete mark is than set to true for that node. Finally the pointers of the parent nodes of the deleted node are updated. If the concurrent access to a priority queue is allowed, conflicts may arise between two processes. For example, a conflict arises if one process is trying to insert a new node, but at the same time another process is about to delete the predecessor of that node. The rest of this section discusses a queue based algorithm on distributed memory. We assume each processor has its own local memory and a local (sequential) priority queue. The elements of the global (parallel) priority queue are distributed across all processors. A k insert operation assigns the elements uniformly random to the processors which insert the elements into their local queues. Note that single elements can still be inserted into the queue. Using this strategy the global smallest elements are in the union of the local smallest elements of every processor with high probability. Thus each processor holds a representative part of the global priority queue. This property is used when k extract min is executed, as the smallest elements of each local queue are removed and collected in a result set. The elements in the result set are still associated with their original processor. The number of elements that is removed from each local queue depends on and the number of processors

By parallel selection the smallest elements of the result set are determined. With high probability these are the global smallest elements. If not, elements are again removed from each local queue and put into the result set. This is done until the global smallest elements are in the result set. Now these elements can be returned. All other elements of the result set are inserted back into their local queues. The running time of k extract min is expected , where and is the size of the priority queue. The priority queue can be further improved by not moving the remaining elements of the result set directly back into the local queues after a k extract min operation. This saves moving elements back and forth all the time between the result set and the local queues. By removing several elements at once a considerable speedup can be reached. But not all algorithms can use this kind of priority queue. Dijkstra's algorithm for example can not work on several nodes at once. The algorithm takes the node with the smallest distance from the priority queue and calculates new distances for all its neighbor nodes. If you would take out nodes, working at one node could change the distance of another one of the nodes. So using k element operations destroys the label setting property of Dijkstra's algorithm.