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

Очередь с приоритетом (англ. priority queue) — абстрактный тип данных в программировании, поддерживающий три операции:

• InsertWithPriority: добавить в очередь элемент с нaзначенным приоритетом
• GetNext: извлечь из очереди и вернуть элемент с минимальным приоритетом (другие названия «PopElement(Off)» или «GetMinimum»)
• PeekAtNext (необязательная операция): просмотреть элемент с минимальным приоритетом без извлечения

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

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

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

Если очередь пуста, то можно считать, что операции MIN и EXTRACT_MIN возвращают некоторую специальную константу UNDEF.

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

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

Примеры

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

Начальник добавляет задачи в список, указывая их приоритет, то есть выполняет операцию INSERT.

Расширения очереди с приоритетом

Различные реализации очереди с приоритетом нередко расширяют её интерфейс следующими операциями:

• DELETE(k) — удалить пару с ключом k;
• CHANGE_KEY(k, k_new) — в первой паре с ключом k заменить ключ на k_new;
• UNION(queue1, queue2) — из двух очередей с приоритетом сделать одну, объединив множества хранимых в них пар.

См. также

• Реализации очереди с приоритетом

• Двоичная куча
• Биномиальная куча
• Фибоначчиева куча

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд.. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
• Джейсуол Н. К. Очереди с приоритетами = Priority queues. — М.: Мир, 1973. — 279 с.

Ссылки

• С++ STL priority_queue:

• страница помощи std::priority_queue на MSDN
• страница помощи std::priority_queue на SGI

• Очереди с приоритетом для Ruby:

• Brian Amberg’s priority-queue
• PriorityQueue в Ruby Application Archive