Русская Википедия:Очередь с приоритетом (программирование)
Шаблон:Значения2 Очередь с приоритетом (Шаблон:Lang-en) — абстрактный тип данных в программировании, поддерживающий две обязательные операции — добавить элемент и извлечь максимумШаблон:Sfn (минимум). Предполагается, что для каждого элемента можно вычислить его приоритет — действительное число или в общем случае элемент линейно упорядоченного множестваШаблон:Sfn.
Описание
Основные методы, реализуемые очередью с приоритетом, следующиеШаблон:SfnШаблон:SfnШаблон:Sfn:
insert(ключ, значение)— добавляет пару(ключ, значение)в хранилище;extract_minimum()— возвращает пару(ключ, значение)с минимальным значением ключа, удаляя её из хранилища.
При этом меньшее значение ключа соответствует более высокому приоритету.
В некоторых случаях более естественен рост ключа вместе с приоритетом. Тогда второй метод можно назвать extract_maximum()Шаблон:Sfn.
Есть ряд реализаций, в которых обе основные операции выполняются в худшем случае за время, ограниченное <math>O(\log n)</math> (см. «O» большое и «o» малое), где <math>n</math> — количество хранимых пар.
Примеры
В качестве примера очереди с приоритетом можно рассмотреть список задач работника. Когда он заканчивает одну задачу, он переходит к очередной — самой приоритетной (ключ будет величиной, обратной приоритету) — то есть выполняет операцию извлечения максимума. Начальник добавляет задачи в список, указывая их приоритет, то есть выполняет операцию добавления элемента.
Расширения очереди с приоритетом
На практике интерфейс очереди с приоритетом нередко расширяют другими операциями[1]Шаблон:Sfn:
- вернуть минимальный элемент без удаления из очереди
- изменить приоритет произвольного элемента
- удалить произвольный элемент
- слить две очереди в одну
В индексированных очередях с приоритетом (адресуемыхШаблон:Sfn) возможно обращение к элементам по индексу. Такие очереди могут быть использованы, например, для слияния нескольких отсортированных последовательностей (multiway merge)Шаблон:Sfn.
Могут также рассматриваться очереди с приоритетом с двусторонним доступом (Шаблон:Lang-en), в которых есть операции доступа как к минимальному, так и к максимальному элементуШаблон:Sfn.
Реализации
Очередь с приоритетами может быть реализована на основе различных структур данных.
Простейшие (и не очень эффективные) реализации могут использовать неупорядоченный или упорядоченный массив, связный список, подходящие для небольших очередей. При этом вычисления могут быть как «ленивыми» (тяжесть вычислений переносится на извлечение элемента), так и ранними (eager), когда вставка элемента сложнее его извлечения. То есть, одна из операций может быть произведена за время <math>O(1)</math>, а другая — в худшем случае за <math>O(N)</math>, где <math>N</math> — длина очередиШаблон:Sfn.
Более эффективными являются реализации на основе кучи, где обе операции можно производить в худшем случае за время <math>O(\log N)</math>Шаблон:Sfn. К ним относятся двоичная куча, биномиальная куча, фибоначчиева куча, Шаблон:Нп3Шаблон:Sfn.
Абстрактный тип данных (АТД) для очереди с приоритетом получается из АТД кучи переименованием соответствующих функций. Минимальное (максимальное) значение находится всегда на вершине кучиШаблон:Sfn.
Пример на Python
Стандартная библиотека Python содержит модуль heapq[2], реализующий очередь с приоритетом[3]:
# импорт двух функций очереди под именами, принятыми в данной статье
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])
Этот пример выведет слово «heap».
Примечания
Литература
- Шаблон:Книга
- Шаблон:Книга, 4.10. Очереди с приоритетами
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
Ссылки
- Очереди с приоритетом для Ruby:
