Очередь с приоритетом (программирование)
Очередь с приоритетом (англ. priority queue) — абстрактный тип данных в программировании, поддерживающий две обязательные операции — добавить элемент и извлечь максимум[1] (минимум). Предполагается, что для каждого элемента можно вычислить его приоритет — действительное число или в общем случае элемент линейно упорядоченного множества[2].
В некоторых случаях более естественен рост ключа вместе с приоритетом. Тогда второй метод можно назвать extract_maximum()[1].
Есть ряд реализаций, в которых обе основные операции выполняются в худшем случае за время, ограниченное (см. «O» большое и «o» малое), где — количество хранимых пар.
В качестве примера очереди с приоритетом можно рассмотреть список задач работника. Когда он заканчивает одну задачу, он переходит к очередной — самой приоритетной (ключ будет величиной, обратной приоритету) — то есть выполняет операцию извлечения максимума. Начальник добавляет задачи в список, указывая их приоритет, то есть выполняет операцию добавления элемента.
В индексированных очередях с приоритетом (адресуемых[5]) возможно обращение к элементам по индексу. Такие очереди могут быть использованы, например, для слияния нескольких отсортированных последовательностей (multiway merge)[1].
Могут также рассматриваться очереди с приоритетом с двусторонним доступом (англ. double-ended priority queue, DEPQ), в которых есть операции доступа как к минимальному, так и к максимальному элементу[6].