На этом шаге мы дадим краткую характеристику таким очередям.
Очередь с приоритетом представляет собой контейнерную структуру данных, которая управляет набором записей с полностью упорядоченными ключами (например, числовым значением веса) с целью обеспечения быстрого доступа к записи с наименьшим или наибольшим ключом в наборе.
См. Википедию "Полная упорядоченность": https://en.wikipedia.org/wiki/Total_order и
https://ru.wikipedia.org/wiki/Линейно_упорядоченное_множество.
Очередь с приоритетом можно представить как видоизмененную очередь: вместо получения следующего элемента по времени вставки она получает элемент с самым высоким приоритетом. Приоритет отдельных элементов определяется примененным к их ключам упорядочением.
Очереди с приоритетом широко используются для решения задач планирования, например предоставления предпочтений задачам с более высокой актуальностью.
Представьте работу планировщика задач операционной системы:
В идеальном случае высокоприоритетные задачи в системе (например, игра в компьютерную игру в реальном времени) должны иметь предпочтение перед задачами с более низким приоритетом (например, скачивание обновлений в фоновом режиме). Организовывая предстоящие задачи в очередь с приоритетом, которая использует актуальность задачи в качестве ключа, планировщик задач может быстро выбирать задачи с самым высоким приоритетом и давать им выполняться в первую очередь.
Начиная с этого шага вы увидите несколько вариантов реализации очередей с приоритетом в Python с помощью встроенных структур данных либо структур данных, которые поставляются вместе со стандартной библиотекой Python. Каждая реализация будет иметь свои собственные преимущества и недостатки, но, по нашему мнению, в каждом распространенном сценарии есть свой победитель. Давайте узнаем, что лучше.
На следующем шаге мы рассмотрим класс list.
