Определения

Очередь с приоритетом (priority queue) — это абстрактный тип данных, в котором порядок извлечения элементов определяется не временем их добавления, а значением приоритета. Элемент с наивысшим (или наименьшим, в зависимости от реализации) приоритетом обрабатывается первым. Такой подход предоставляет разработчику больше гибкости, чем обычная сортировка, т. к. позволяет вводить новые элементы в систему в произвольном месте. Вставить новый элемент в нужное место в очереди с приоритетами может оказаться намного эффективнее, чем сортировать заново все элементы при каждой вставке.

Базовая очередь с приоритетами поддерживает три основные операции:

• insert (Q, x) - вставляет в очередь с приоритетами о элемент х;
• find-minimum(Q) и find-maximum(Q) - возвращает указатель на элемент с наименьшим (наибольшим) значением ключа среди всех ключей в очереди с приоритетами Q;
• delete-minimum(Q) и delete-maximum (Q) - удаляет из очереди с приоритетами о элемент с наименьшим (наибольшим) значением ключа.

Примеры и применения

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

Очереди с приоритетом широко используются в различных областях:

• Алгоритмы на графах. Например, в алгоритме Дейкстры для поиска кратчайшего пути очередь с приоритетом используется для выбора вершины с минимальным расстоянием на каждом шаге.
• Планирование задач. В операционных системах задачи с более высоким приоритетом обрабатываются раньше фоновых.
• Симуляции и оптимизация. Обработка элементов на основе их важности или времени поступления.
• Сетевые технологии. Приоритизация трафика в маршрутизаторах и коммутаторах, где критически важные пакеты обрабатываются в первую очередь.

Литература

[ Скиена 2022 с. 115]

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