Главная
Новости
Статьи
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




17.10.2021


17.10.2021


16.10.2021


15.10.2021


15.10.2021


14.10.2021


14.10.2021





Яндекс.Метрика

Очередь с приоритетом (программирование)

28.09.2021

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

Описание

Основные методы, реализуемые очередью с приоритетом, следующие:

  • insert(ключ, значение) — добавляет пару (ключ, значение) в хранилище;
  • extract_minimum() — возвращает пару (ключ, значение) с минимальным значением ключа, удаляя её из хранилища.

При этом меньшее значение ключа соответствует более высокому приоритету.

В некоторых случаях более естественен рост ключа вместе с приоритетом. Тогда второй метод можно назвать extract_maximum().

Есть ряд реализаций, в которых обе основные операции выполняются в худшем случае за время, ограниченное O ( log ⁡ n ) {displaystyle O(log n)} (см. «O» большое и «o» малое), где n {displaystyle n} — количество хранимых пар.

Примеры

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

Расширения очереди с приоритетом

На практике интерфейс очереди с приоритетом нередко расширяют другими операциями:

  • вернуть минимальный элемент без удаления из очереди
  • изменить приоритет произвольного элемента
  • удалить произвольный элемент
  • слить две очереди в одну

В индексированных очередях с приоритетом (адресуемых) возможно обращение к элементам по индексу. Такие очереди могут быть использованы, например, для слияния нескольких отсортированных последовательностей (multiway merge).

Могут также рассматриваться очереди с приоритетом с двусторонним доступом (англ. double-ended priority queue, DEPQ), в которых есть операции доступа как к минимальному, так и к максимальному элементу.

Реализации

Очередь с приоритетами может быть реализована на основе различных структур данных.

Простейшие (и не очень эффективные) реализации могут использовать неупорядоченный или упорядоченный массив, связный список, подходящие для небольших очередей. При этом вычисления могут быть как «ленивыми» (тяжесть вычислений переносится на извлечение элемента), так и ранними (eager), когда вставка элемента сложнее его извлечения. То есть, одна из операций может быть произведена за время O ( 1 ) {displaystyle O(1)} , а другая — в худшем случае за O ( N ) {displaystyle O(N)} , где N — длина очереди.

Более эффективными являются реализации на основе кучи, где обе операции можно производить в худшем случае за время O ( log ⁡ N ) {displaystyle O(log N)} . К ним относятся двоичная куча, биномиальная куча, фибоначчиева куча, pairing heap.

Абстрактный тип данных (АТД) для очереди с приоритетом получается из АТД кучи переименованием соответствующих функций. Минимальное (максимальное) значение находится всегда на вершине кучи.

Пример на Python

Стандартная библиотека Python содержит модуль heapq, реализующий очередь с приоритетом:

# импорт двух функций очереди под именами, принятыми в данной статье 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».


Имя:*
E-Mail:
Комментарий: