Приоритетная очередь
Приоритетная очередь — это абстрактная структура данных, в которой каждый элемент имеет определённый приоритет. В отличие от обычной очереди, работающей по принципу «первым пришёл — первым обслужен» (FIFO), из приоритетной очереди элемент с наивысшим приоритетом извлекается первым, независимо от времени его поступления. Если несколько элементов имеют одинаковый приоритет, порядок их извлечения может быть произвольным или определяться дополнительными правилами (например, порядком поступления).
Основные операции
Приоритетная очередь поддерживает три фундаментальные операции:
- insert (или push) — добавление нового элемента с заданным приоритетом.
- extractMax (или pop) — удаление и возврат элемента с наивысшим приоритетом.
- peek (или top) — получение элемента с наивысшим приоритетом без его удаления.
В некоторых реализациях также поддерживаются операции изменения приоритета существующего элемента (decreaseKey или increaseKey) и проверки на пустоту (isEmpty).
Реализации
Двоичная куча
Наиболее распространённая реализация приоритетной очереди — двоичная куча (binary heap). Это полное бинарное дерево, в котором значение каждого узла не меньше (для max-кучи) или не больше (для min-кучи) значений его потомков. Для max-кучи корень всегда содержит максимальный элемент.
- Вставка: элемент помещается в конец массива, затем «всплывает» (sift-up) до своего места.
- Извлечение максимума: корень заменяется последним элементом, который затем «опускается» (sift-down) до восстановления свойства кучи.
- Сложность: обе операции выполняются за O(log n), где n — количество элементов. Построение кучи из n элементов — O(n).
Фибоначчиева куча
Фибоначчиева куча обеспечивает амортизированное время O(1) для вставки и O(log n) для извлечения максимума. Она особенно эффективна для алгоритмов, где требуется много операций уменьшения приоритета (например, алгоритм Дейкстры). Однако из-за сложности реализации и больших констант на практике применяется реже.
Другие структуры
- Биномиальная куча — поддерживает быстрое слияние двух очередей (O(log n)).
- Splay-дерево — саморегулирующееся двоичное дерево поиска, может использоваться как приоритетная очередь с амортизированным O(log n) на операцию.
- Куча Бродала — теоретически оптимальная структура с O(1) на вставку и O(log n) на извлечение минимума, но крайне сложна для практического применения.
Применение
Приоритетные очереди широко используются в различных областях информатики и программирования.
Алгоритмы на графах
- Алгоритм Дейкстры для поиска кратчайших путей. Приоритетная очередь хранит вершины, упорядоченные по текущему расстоянию от начальной вершины.
- Алгоритм Прима для построения минимального остовного дерева. Очередь хранит рёбра или вершины, упорядоченные по весу.
- Алгоритм A\* для поиска пути с эвристикой.
Операционные системы
- Планировщик задач (scheduler). Процессы и потоки помещаются в приоритетную очередь, и процессор выделяется задаче с наивысшим приоритетом.
- Обработка прерываний. Прерывания с более высоким приоритетом обрабатываются раньше.
Сети и передача данных
- Маршрутизация пакетов. Пакеты с более высоким приоритетом (например, голосовой трафик) передаются раньше.
- Очереди в сетевых коммутаторах для обеспечения качества обслуживания (QoS).
Моделирование и симуляция
- Дискретно-событийное моделирование. События упорядочиваются по времени наступления. Приоритетная очередь позволяет эффективно извлекать ближайшее событие.
Сжатие данных
- Алгоритм Хаффмана для построения оптимального префиксного кода. Приоритетная очередь используется для хранения узлов дерева, упорядоченных по частоте символов.
Приоритетная очередь в стандартных библиотеках
Многие языки программирования предоставляют встроенные реализации приоритетной очереди:
- C++:
std::priority_queue(по умолчанию max-куча). - Java:
java.util.PriorityQueue(min-куча). - Python:
heapq(min-куча, реализована как список с операциямиheappushиheappop). - C#:
System.Collections.Generic.PriorityQueue<TElement, TPriority>(с .NET 6). - Rust:
std::collections::BinaryHeap(max-куча).
Сравнение с другими структурами данных
| Структура | Вставка | Извлечение | Поиск | Примечание |
|---|---|---|---|---|
| Приоритетная очередь (куча) | O(log n) | O(log n) | O(n) | Нет быстрого поиска произвольного элемента |
| Отсортированный массив | O(n) | O(1) | O(log n) | Быстрое извлечение, медленная вставка |
| Неотсортированный массив | O(1) | O(n) | O(n) | Быстрая вставка, медленное извлечение |
| Сбалансированное дерево поиска | O(log n) | O(log n) | O(log n) | Поддерживает все операции, но сложнее в реализации |
Интересные факты
- Термин «приоритетная очередь» впервые был использован в 1964 году в работе Роберта Флойда и Джона Уильямса, которые также предложили алгоритм пирамидальной сортировки (heapsort), основанный на двоичной куче.
- В 1984 году Майкл Фредман и Роберт Тарьян разработали фибоначчиеву кучу, которая до сих пор остаётся одной из самых эффективных структур для приоритетных очередей в теоретическом плане.
- В некоторых системах реального времени (RTOS) приоритетные очереди реализованы на аппаратном уровне для обеспечения детерминированного времени выполнения операций.
Источники
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы: построение и анализ» (CLRS), глава 6 «Пирамидальная сортировка и очередь с приоритетами».
- Дональд Кнут. «Искусство программирования», том 3 «Сортировка и поиск».
- Michael L. Fredman, Robert E. Tarjan. «Fibonacci heaps and their uses in improved network optimization algorithms» (1984).
- Стандарт ISO/IEC 14882:2020 (C++20), раздел 24.6.7 «Class template priority_queue».
- Документация Python 3.12: модуль
heapq.
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →