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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

См. также

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

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

Ссылки

• С++ STL priority_queue:

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

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

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

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