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


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

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

  • InsertWithPriority: добавить в очередь элемент с нaзначенным приоритетом
  • GetNext: извлечь из очереди и вернуть элемент с минимальным приоритетом (другие названия «PopElement(Off)» или «GetMinimum»)
  • PeekAtNext (необязательная операция): просмотреть элемент с наивысшим приоритетом без извлечения

Говоря другим языком, очередь с приоритетом позволяет хранить пары (ключ, значение) и поддерживает операции добавления пары, поиска пары с минимальным ключом и извлечения пары с минимальным ключом:

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

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

Если очередь пуста, то можно считать, что операции MIN и EXTRACT_MIN возвращают некоторую специальную константу UNDEF.

В разных реализациях очереди с приоритетом семантика и названия операций могут отличаться.

Есть ряд реализаций в которых все три операции выполняются в худшем случае за время, ограниченное O(\log n) (см. «O» большое и «o» малое), где n — количество хранимых пар. Реализация «Фибоначчиева куча» интересна тем, что в среднем (амортизационно) эти три операции выполняет за время O(1) и, кроме того, позволяет быстро (тоже за время O(1)) выполнять дополнительную операцию слияния двух куч.

Примеры

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

Начальник добавляет задачи в список, указывая их приоритет, то есть выполняет операцию INSERT.

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

Различные реализации очереди с приоритетом нередко расширяют её интерфейс следующими операциями:

  • DELETE(k) — удалить пару с ключом k;
  • CHANGE_KEY(k, k_new) — в первой паре с ключом k заменить ключ на k_new;
  • UNION(queue1, queue2) — из двух очередей с приоритетом сделать одну, объединив множества хранимых в них пар.

См. также

  • Реализации очереди с приоритетом

Литература

  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд.. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
  • Джейсуол Н. К. Очереди с приоритетами = Priority queues. — М.: Мир, 1973. — 279 с.

Ссылки

  • Очереди с приоритетом для Ruby:



Wikimedia Foundation. 2010.

Смотреть что такое "Очередь с приоритетом" в других словарях:

  • Очередь (программирование) — У этого термина существуют и другие значения, см. Очередь. Очередь  структура данных с дисциплиной доступа к элементам «первый пришёл  первый вышел» (FIFO, First In  First Out). Добавление элемента (принято обозначать словом… …   Википедия

  • многоприоритетная очередь — очередь с многоприоритетным обслуживанием Очередь, в которой все поступающие пакеты (запросы) заносятся в несколько списков с разными категориями срочности доставки (приоритетами), причем первыми всегда считываются данные из списка с более… …   Справочник технического переводчика

  • Честная очередь с весовыми коэффициентами — (англ. Weighted fair queuing, WFQ)  механизм планирования пакетных потоков данных с различными приоритетами. Его целью является регулировать использования одного канала передачи данных несколькими конкурирующими потоками. В данном… …   Википедия

  • Взвешенная справедливая очередь — (англ. Weighted fair queuing, WFQ)  механизм планирования пакетных потоков данных с различными приоритетами. Его целью является регулировать использования одного канала передачи данных несколькими конкурирующими потоками. В данном… …   Википедия

  • Алгоритм поиска A* — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… …   Википедия

  • А* — Алгоритмы поиска на графах A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению Поиск A* (произносится «А звездочка») в информатике и математике, алгоритм …   Википедия

  • FIFO — У этого термина существуют и другие значения, см. FIFO и LIFO. FIFO планировщик проц …   Википедия

  • FIFO (информатика) — У этого термина существуют и другие значения, см. FIFO. FIFO акроним First In, First Out («первым пришёл первым ушёл», англ. ), абстрактное понятие в способах организации и манипулирования данными относительно времени и приоритетов. Это… …   Википедия

  • Фибоначчиева куча — У этого термина существуют и другие значения, см. Куча (значения). Фибоначчиева куча (англ. Fibonacci heap) структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы… …   Википедия

  • Список структур данных — …   Википедия

Книги