Очередь приоритетов¶

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

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

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

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

Дополнительно могут быть реализованы операции:

• Change-Priority — изменение приоритета существующего элемента.
• Delete — удаление произвольного элемента.
• Merge — слияние двух очередей приоритетов в одну.

Очередь приоритетов может быть реализована как max-очередь (извлекается максимальный элемент) или min-очередь (извлекается минимальный). Выбор зависит от задачи: например, в алгоритме Дейкстры для поиска кратчайших путей используется min-очередь, а в симуляциях событий — max-очередь (по времени события).

¶Реализации

¶Куча (heap)

Наиболее распространённая реализация очереди приоритетов — бинарная куча (binary heap). Это полное бинарное дерево, удовлетворяющее свойству кучи: для max-кучи значение каждого узла не меньше значений его дочерних узлов, для min-кучи — не больше. Операции Insert и Extract-Max выполняются за O(log n), где n — количество элементов. Peek — за O(1). Бинарная куча компактно хранится в массиве: для узла с индексом i его левый дочерний узел находится по индексу 2i+1, правый — 2i+2, родительский — по индексу floor((i-1)/2).

Существуют и другие виды куч:

• Фибоначчиева куча (Fibonacci heap) — позволяет выполнять Insert и Merge за O(1) амортизированно, а Extract-Min — за O(log n). Используется в алгоритмах, где требуется много операций слияния, например, в алгоритме Прима для минимального остовного дерева.
• Куча Бродала (Brodal queue) — теоретическая реализация с гарантированно оптимальными асимптотическими оценками, но сложная для практического применения.
• D-куча (d-ary heap) — обобщение бинарной кучи, где каждый узел имеет d дочерних узлов. Уменьшает высоту дерева, но увеличивает время сравнения при Extract-Min.

¶Другие структуры

• Сортированный список (sorted list) — операции Insert и Extract-Min могут быть O(n) в худшем случае, но при использовании сбалансированных деревьев поиска (например, красно-черных деревьев) — O(log n).
• Несортированный список — Insert за O(1), Extract-Min за O(n).
• Биномиальная куча (binomial heap) — поддерживает Merge за O(log n), Insert и Extract-Min — за O(log n).
• Очередь с приоритетом на основе массива — для небольших фиксированных наборов данных может быть эффективна простой линейный поиск.

¶Применение

¶Алгоритмы на графах

Очередь приоритетов является ключевым компонентом многих алгоритмов:

• Алгоритм Дейкстры — для поиска кратчайших путей от одной вершины. Использует min-очередь для выбора вершины с минимальным текущим расстоянием.
• Алгоритм Прима — для построения минимального остовного дерева. Использует min-очередь для выбора ребра с минимальным весом.
• Алгоритм A\* — для поиска пути в игровых и навигационных системах. Использует очередь с приоритетом по эвристической оценке.

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

• Планирование процессов — очереди приоритетов используются для управления очередями процессов с разными приоритетами (например, в алгоритмах планирования с приоритетами, таких как Multilevel Feedback Queue).
• Управление прерываниями — аппаратные и программные прерывания обрабатываются в порядке приоритета.

¶Симуляция и моделирование

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

¶Компьютерные сети

• Маршрутизация — в протоколах, таких как OSPF (Open Shortest Path First), используется алгоритм Дейкстры с очередью приоритетов.
• Управление трафиком — QoS (Quality of Service) очереди с приоритетами для разных типов пакетов (голос, видео, данные).

¶Обработка данных

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

¶Примеры в языках программирования

Многие языки программирования предоставляют встроенные реализации очереди приоритетов:

• C++ — std::priority_queue (по умолчанию max-куча на основе бинарной кучи). Для min-кучи используется std::greater.
• Java — java.util.PriorityQueue (min-куча). Для max-кучи используется Comparator.reverseOrder().
• Python — модуль heapq предоставляет функции для работы с min-кучей (например, heapq.heappush, heapq.heappop).
• C# — System.Collections.Generic.PriorityQueue<TElement, TPriority> (с .NET 6).
• Go — стандартная библиотека container/heap предоставляет интерфейс для реализации кучи на произвольном типе данных.

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

• Термин «куча» (heap) в контексте структуры данных был введён Дж. У. Дж. Уильямсом в 1964 году, который также изобрёл пирамидальную сортировку.
• Фибоначчиева куча была разработана Майклом Фредманом и Робертом Тарьяном в 1984 году. Её название связано с тем, что в анализе амортизированной сложности используются числа Фибоначчи.
• В некоторых приложениях, где требуется высокая производительность, используются специализированные реализации, такие как календарная очередь (calendar queue) или косая куча (skew heap), которые оптимизированы для конкретных паттернов доступа.

¶Критика и ограничения

• Амортизированная сложность — для некоторых реализаций (например, Фибоначчиевой кучи) гарантии сложности являются амортизированными, что может быть неприемлемо в системах реального времени.
• Память — кучи на основе массивов эффективны по памяти, но плохо подходят для динамических данных с частыми вставками и удалениями в произвольных местах.
• Параллелизм — стандартные реализации не являются потокобезопасными. Для многопоточных приложений требуются блокировки или специализированные lock-free структуры (например, concurrent priority queue).

¶Источники

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание, 2009.
• Дональд Кнут. «Искусство программирования», том 3: «Сортировка и поиск», 2-е издание, 1998.
• Michael L. Fredman, Robert E. Tarjan. «Fibonacci heaps and their uses in improved network optimization algorithms», Journal of the ACM, 1987.
• Документация стандартных библиотек C++, Java, Python, Go.