WikiSort.ru - Программирование

Очередь с приоритетом (англ. 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)}$ , где N — длина очереди^[1].

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

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

# импорт двух функций очереди под именами, принятыми в данной статье
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])

Примечания

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = 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.

Ссылки

• С++ STL priority_queue:

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

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

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

• Верифицированная с помощью Coq реализация очереди с приоритетом для Haskell:

• Implementation and verification of priority queues