Очередь с приоритетами
Общие сведения
Очередь с приоритетами (англ. priority queue) — абстрактный контейнер, похожий на обычную очередь, но имеющий ряд особенностей:
- Каждому элементу очереди с приоритетами сопоставлено некоторое значение, именуемое приоритетом этого элемента. Приоритеты допускают сравнение друг с другом;
- Функция извлечения из очереди с приоритетами возвращает тот элемент, приоритет которого является максимальным.
Учащийся, выполняющий домашнее задание по нескольким предметам, может вводить различные показатели, определяющие порядок выполнения: от более любимых предметов к менее любимым, от менее сложных к более сложным, и так далее. Пожарная блигада планирует выезды сообразно с категорией сложности возгорания. Операционная система компьютера выделяет аппаратные ресурсы в первую очередь приложениям, запущенным с приоритетом реального времени, и лишь затем — остальным приложениям. Эти примеры позволяют пояснить назначение и принципы функционирования очередей с приоритетами.
Интерфейс
Интерфейс очереди с приоритетами в целом аналогичен интерфейсу обычной очереди, но в операции добавления появляется второй аргумент, а операция удаления возвращает элемент с наибольшим приоритетом:
| void enqueue(T1 value, T2 priority) | — вставка элемента value с приоритетом priority в очередь; |
| T1 dequeue() | — извлечение элемента с максимальным приоритетом из очереди; |
| bool isEmpty() | — проверка очереди на отсутствие элементов. |