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

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

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

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

• insert (или push) — добавление нового элемента с заданным приоритетом.
• extract_max (или pop, extract_min) — удаление и возврат элемента с наивысшим (или наинизшим) приоритетом.
• peek (или top) — получение значения элемента с наивысшим приоритетом без его удаления.

Дополнительные операции могут включать:

• increase_key — изменение приоритета уже находящегося в очереди элемента (обычно в сторону повышения).
• decrease_key — изменение приоритета в сторону понижения.
• delete — удаление произвольного элемента из очереди.
• merge — объединение двух очередей с приоритетами в одну.

Реализации

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

Двоичная куча (Binary Heap)

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

• insert: O(log n)
• extract_max: O(log n)
• peek: O(1)
• increase_key: O(log n)

Двоичная куча лежит в основе алгоритма пирамидальной сортировки (heapsort) и является стандартной реализацией очереди с приоритетом во многих языках программирования (например, heapq в Python, PriorityQueue в Java, std::priority_queue в C++).

Биномиальная куча (Binomial Heap)

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

• insert: O(log n) (амортизированная O(1))
• extract_max: O(log n)
• merge: O(log n)

Куча Фибоначчи (Fibonacci Heap)

Более сложная структура, обеспечивающая очень быструю вставку и изменение ключа за счёт отложенных операций.

• insert: O(1) (амортизированная)
• extract_max: O(log n) (амортизированная)
• decrease_key: O(1) (амортизированная)

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

Сортирующее дерево (Binary Search Tree)

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

• insert: O(log n)
• extract_max: O(log n)

Неупорядоченный список (Unsorted List)

Простейшая реализация, при которой элементы хранятся в списке без какого-либо порядка.

• insert: O(1)
• extract_max: O(n) (требуется линейный поиск максимума)

Упорядоченный список (Sorted List)

Элементы хранятся в отсортированном по приоритету порядке.

• insert: O(n) (требуется поиск места вставки)
• extract_max: O(1)

Применение

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

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

• Алгоритм Дейкстры: для поиска кратчайшего пути от одной вершины ко всем остальным. На каждом шаге извлекается вершина с наименьшим текущим расстоянием (приоритетом).
• Алгоритм Прима: для построения минимального остовного дерева. Извлекается вершина с наименьшим весом ребра, соединяющего её с уже построенным деревом.
• Алгоритм A\*: для поиска кратчайшего пути с эвристикой. Приоритетом является сумма фактической стоимости пути и эвристической оценки.

Планирование процессов (Scheduling)

В операционных системах очереди с приоритетом используются для планирования выполнения процессов и потоков. Процессам с более высоким приоритетом (например, системным задачам) выделяется процессорное время раньше, чем процессам с низким приоритетом.

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

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

Сжатие данных (алгоритм Хаффмана)

При построении оптимального префиксного кода (кода Хаффмана) используется очередь с приоритетом для многократного объединения двух символов с наименьшими частотами.

Обработка потоковых данных

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

Игровые движки

В компьютерных играх очереди с приоритетом используются для управления AI-агентами, обработки коллизий, рендеринга объектов в порядке удалённости от камеры и других задач.

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

Min-heap vs Max-heap

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

Статическая vs динамическая

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

С возможностью изменения приоритета

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

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

• Термин «очередь с приоритетом» ввёл в научный обиход американский учёный Роберт Флойд в 1964 году, хотя сама концепция использовалась и ранее.
• Двоичная куча была впервые описана Джоном Уильямсом в 1964 году для алгоритма пирамидальной сортировки.
• Куча Фибоначчи была разработана Майклом Фредманом и Робертом Тарьяном в 1984 году. Название происходит от чисел Фибоначчи, которые используются в анализе её амортизированной сложности.
• В стандартной библиотеке языка C++ (std::priority_queue) по умолчанию используется max-heap на основе двоичной кучи. Для получения min-heap необходимо указать компаратор std::greater.
• В языке Python модуль heapq реализует min-heap (наименьший элемент извлекается первым). Для имитации max-heap часто используют отрицательные значения приоритетов.
• В языке Java класс PriorityQueue по умолчанию реализует min-heap. Для создания max-heap используется компаратор Collections.reverseOrder().

Источники

• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание. Глава 6: «Пирамидальная сортировка и очереди с приоритетом».
• Дональд Кнут. «Искусство программирования», том 3: «Сортировка и поиск».
• Роберт Седжвик, Кевин Уэйн. «Алгоритмы на Java», 4-е издание. Глава 2.4: «Очереди с приоритетом».
• Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. «Data Structures and Algorithms in Java», 6th edition. Chapter 9: «Priority Queues».
• Статья «Priority queue» в англоязычной Википедии (версия от 15.10.2023).