Очередь с приоритетом (программирование)

Очередь с приоритетом (англ. priority queue) — абстрактный тип данных в программировании, поддерживающий две обязательные операции — добавить элемент и извлечь максимум^[1] (минимум). Предполагается, что для каждого элемента можно вычислить его приоритет — действительное число или в общем случае элемент линейно упорядоченного множества^[2].

Основные методы, реализуемые очередью с приоритетом, следующие^[2][3][1]:

• insert(ключ, значение) — добавляет пару (ключ, значение) в хранилище;
• extract_minimum() — возвращает пару (ключ, значение) с минимальным значением ключа, удаляя её из хранилища.

При этом меньшее значение ключа соответствует более высокому приоритету.

В некоторых случаях более естественен рост ключа вместе с приоритетом. Тогда второй метод можно назвать extract_maximum()^[1].

Есть ряд реализаций, в которых обе основные операции выполняются в худшем случае за время, ограниченное ${\displaystyle O(\log n)}$ (см. «O» большое и «o» малое), где ${\displaystyle n}$ — количество хранимых пар.

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

На практике интерфейс очереди с приоритетом нередко расширяют другими операциями^[4][3]:

• вернуть минимальный элемент без удаления из очереди
• изменить приоритет произвольного элемента
• удалить произвольный элемент
• слить две очереди в одну

В индексированных очередях с приоритетом (адресуемых^[5]) возможно обращение к элементам по индексу. Такие очереди могут быть использованы, например, для слияния нескольких отсортированных последовательностей (multiway merge)^[1].

Могут также рассматриваться очереди с приоритетом с двусторонним доступом (англ. double-ended priority queue, DEPQ), в которых есть операции доступа как к минимальному, так и к максимальному элементу^[6].

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

Простейшие (и не очень эффективные) реализации могут использовать неупорядоченный или упорядоченный

, подходящие для небольших очередей. При этом вычисления могут быть как «ленивыми» (тяжесть вычислений переносится на извлечение элемента), так и ранними (eager), когда вставка элемента сложнее его извлечения. То есть, одна из операций может быть произведена за время ${\displaystyle O(1)}$, а другая — в худшем случае за ${\displaystyle O(N)}$, где ${\displaystyle N}$ — длина очереди

Более эффективными являются реализации на основе кучи, где обе операции можно производить в худшем случае за время ${\displaystyle O(\log N)}$^[1]. К ним относятся двоичная куча, биномиальная куча, фибоначчиева куча, pairing heap^{[англ.][6]}.

Абстрактный тип данных (АТД) для очереди с приоритетом получается из АТД кучи переименованием соответствующих функций. Минимальное (максимальное) значение находится всегда на вершине кучи^[7].

Стандартная библиотека Python содержит модуль heapq^[8], реализующий очередь с приоритетом^[9]:

# импорт двух функций очереди под именами, принятыми в данной статье
from heapq import heappush as insert, heappop as extract_maximum
pq = []  # инициализация списка
insert(pq, (4, 0, "p"))   # вставка в очередь элемента "p" с индексом 0 и приоритетом 4
insert(pq, (2, 1, "e"))
insert(pq, (3, 2, "a"))
insert(pq, (1, 3, "h"))
# вывод четырёх элементов в порядке возрастания приоритетов
print(extract_maximum(pq)[-1] + extract_maximum(pq)[-1] + extract_maximum(pq)[-1] + extract_maximum(pq)[-1])

Этот пример выведет слово «heap».

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд.. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
• Ахо А. В, Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и алгоритмы = Data Structures and Algorithms. — Вильямс, 2000. — 384 с. — ISBN 9785845901224., 4.10. Очереди с приоритетами
• Robert Sedgewick; Kevin Wayne. 2.4 Priority Queues // Algorithms. — Fourth Edition. — Addison-Wesley Professional, 2011. — 992 с. — ISBN 978-0-13-276257-1.
• Gerth Stølting Brodal, Chris Okasaki. Optimal Purely Functional Priority Queues // BRICS Report Series. — Department of Computer Science University of Aarhus, 1996. — № RS-96-37. —
  ISSN 0909-0878
  .
• Fethi Rabhi and Lapalme, G. Algorithms: A Functional Programming Approach. — Addison-Wesley, 1999. — P. 92—93, 106-107. — 235 p. — ISBN 9780201596045.
• Sartaj Sahni and Dinesh P. Mehta. Part II: Priority Queues // Handbook of Data Structures and Applications. — 2nd ed. — Chapman and Hall/CRC, 2018. — 1100 p. — ISBN 9781498701853.
• Mehlhorn, Kurt, Sanders, Peter. 6. Priority Queues // Algorithms and Data Structures: The Basic Toolbox. — Springer, 2008. — 300 с. — ISBN 978-3-540-77978-0.

• C++ STL priority_queue:
  • страница помощи std::priority_queue на MSDN Архивная копия от 12 июня 2009 на Wayback Machine
  • страница помощи std::priority_queue на SGI Архивная копия от 12 мая 2008 на Wayback Machine
• Очереди с приоритетом для Ruby:
  • Brian Amberg’s priority-queue Архивная копия от 1 июля 2007 на Wayback Machine
  • PriorityQueue в Ruby Application Archive Архивная копия от 3 августа 2008 на Wayback Machine
• Верифицированная с помощью Coq реализация очереди с приоритетом для Haskell:
  • Implementation and verification of priority queues Архивная копия от 24 декабря 2014 на Wayback Machine