Очередь с приоритетами¶

Очередь с приоритетами — это абстрактный тип данных (ADT) в информатике, представляющий собой коллекцию элементов, каждый из которых имеет связанный с ним приоритет. В отличие от обычной очереди (FIFO, «первым пришёл — первым вышел»), извлечение элемента из очереди с приоритетами всегда происходит по наибольшему (или наименьшему) приоритету, независимо от порядка добавления. Элемент с наивысшим приоритетом всегда обслуживается первым. Если несколько элементов имеют одинаковый приоритет, порядок их обслуживания может быть произвольным или определяться дополнительными правилами (например, порядком поступления).

¶Основные операции

Очередь с приоритетами поддерживает три базовые операции:

• Insert (или push, enqueue) — добавление нового элемента с заданным приоритетом.
• Extract-Max (или Extract-Min, pop, dequeue) — удаление и возврат элемента с наибольшим (или наименьшим) приоритетом.
• Peek (или Find-Max, Find-Min, top) — получение элемента с наибольшим (или наименьшим) приоритетом без его удаления.

Дополнительно могут поддерживаться операции изменения приоритета элемента (decrease-key, increase-key), удаления произвольного элемента, слияния двух очередей.

¶Реализации

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

¶Неупорядоченный список (массив)

Простейшая реализация: элементы хранятся в списке или массиве без какой-либо сортировки. Операция Insert выполняется за O(1) (добавление в конец), а Extract-Max требует линейного просмотра всех элементов для поиска максимума — O(n). Реализация неэффективна для частых извлечений.

¶Упорядоченный список (массив)

Элементы хранятся в отсортированном по убыванию (или возрастанию) приоритета порядке. Операция Extract-Max выполняется за O(1) (удаление первого элемента), но Insert требует поиска позиции для вставки и сдвига элементов — O(n). Применима, когда число вставок невелико.

¶Бинарная куча (куча)

Наиболее распространённая и эффективная реализация. Бинарная куча — это полное бинарное дерево, удовлетворяющее свойству кучи: для max-кучи приоритет любого узла не меньше приоритетов его потомков. Реализуется на основе массива. Операции Insert и Extract-Max выполняются за O(log n). Peek — за O(1). Бинарная куча является основой для многих алгоритмов (например, пирамидальной сортировки, алгоритма Дейкстры).

¶Биномиальная куча

Биномиальная куча — это набор биномиальных деревьев, каждое из которых удовлетворяет свойству кучи. Поддерживает эффективное слияние двух очередей (merge) за O(log n). Операции Insert и Extract-Max также выполняются за O(log n). Используется в алгоритмах, где требуется частое объединение очередей.

¶Фибоначчиева куча

Фибоначчиева куча — более сложная структура, обеспечивающая амортизированное время O(1) для операций Insert, Decrease-Key и Merge, и O(log n) для Extract-Max. Применяется в алгоритмах, где критично большое количество операций изменения приоритета (например, в алгоритме Дейкстры с большими графами).

¶Двоичная куча (d-арная куча)

Обобщение бинарной кучи, где каждый узел имеет до d потомков. Увеличение d уменьшает высоту дерева (ускоряет Extract-Max), но замедляет Insert из-за большего числа сравнений при просеивании. Параметр d выбирается в зависимости от соотношения операций.

¶Очередь с приоритетами на основе дерева поиска

Сбалансированные деревья поиска (например, красно-чёрные деревья, AVL-деревья) также могут быть использованы для реализации очереди с приоритетами. Операции вставки, удаления и поиска максимума выполняются за O(log n). Однако такая реализация избыточна по сравнению с кучей, так как требует поддержания полной упорядоченности, что не нужно для очереди с приоритетами.

¶Применение

Очередь с приоритетами широко используется в различных областях информатики и программирования:

• Алгоритмы на графах: алгоритм Дейкстры (поиск кратчайших путей), алгоритм Прима (построение минимального остовного дерева), алгоритм A* (поиск пути с эвристикой).
• Операционные системы: планирование процессов (выбор процесса с наивысшим приоритетом для выполнения), управление прерываниями.
• Сетевые технологии: маршрутизация пакетов с приоритетами (Quality of Service, QoS), управление очередями в коммутаторах и маршрутизаторах.
• Сжатие данных: алгоритм Хаффмана (построение оптимального префиксного кода) использует очередь с приоритетами для выбора двух узлов с наименьшими частотами.
• Дискретная оптимизация: алгоритмы ветвей и границ, поиск в пространстве состояний.
• Симуляция событий: в дискретно-событийной симуляции очередь с приоритетами используется для хранения событий, упорядоченных по времени их наступления.
• Обработка данных: в системах реального времени (например, в играх) для обработки объектов с разными приоритетами обновления.

¶Разновидности

¶Max-очередь и Min-очередь

В зависимости от того, какой элемент извлекается первым, различают:

• Max-очередь с приоритетами (max-priority queue) — извлекается элемент с наибольшим приоритетом.
• Min-очередь с приоритетами (min-priority queue) — извлекается элемент с наименьшим приоритетом.

Любая max-очередь может быть преобразована в min-очередь путём инвертирования приоритетов (например, умножением на -1).

¶Двусторонняя очередь с приоритетами

Позволяет извлекать как максимальный, так и минимальный элемент. Реализуется, например, с помощью двух куч (min-куча и max-куча) или с помощью декартова дерева.

¶Очередь с приоритетами с изменяемым приоритетом

Поддерживает операцию изменения приоритета уже добавленного элемента (decrease-key или increase-key). Это необходимо, например, в алгоритме Дейкстры, где приоритет вершины может уменьшаться. Фибоначчиевы кучи оптимизированы под эту операцию.

¶История

Понятие очереди с приоритетами как абстрактного типа данных было формализовано в 1960-х годах. Бинарная куча была впервые описана Дж. Уильямсом в 1964 году в контексте алгоритма пирамидальной сортировки (heapsort). Биномиальные кучи были предложены Жаном Вюйлеменом в 1978 году. Фибоначчиевы кучи разработаны Майклом Фредманом и Робертом Тарьяном в 1984 году. Дальнейшие исследования привели к созданию множества других структур, таких как кучи Бродаля, тонкие кучи, ранговые кучи.

¶Интересные факты

• В стандартной библиотеке языка C++ очередь с приоритетами реализована в виде шаблонного класса std::priority_queue, который по умолчанию использует std::vector и бинарную кучу (max-кучу).
• В Java существует класс PriorityQueue (min-куча), а также PriorityBlockingQueue для многопоточных приложений.
• В Python очередь с приоритетами реализована в модуле heapq (min-куча). Для max-кучи используется инвертирование приоритетов.
• В .NET (C#) очередь с приоритетами появилась в .NET 6 (2021 год) в виде класса PriorityQueue<TElement, TPriority>.
• В языке Go очередь с приоритетами не встроена в стандартную библиотеку, но её можно реализовать с помощью интерфейса heap.Interface.

¶Источники

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (3rd ed.). MIT Press, 2009.
• Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley, 1998.
• Michael L. Fredman, Robert E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 1987.
• Jean Vuillemin. A data structure for manipulating priority queues. Communications of the ACM, 1978.
• J. W. J. Williams. Algorithm 232: Heapsort. Communications of the ACM, 1964.
• Документация стандартной библиотеки C++ (cppreference.com).
• Документация Python (docs.python.org).