Приоритетные очереди

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

Операции

Приоритетные очереди поддерживают следующие операции:

• [math]\mathrm{findMin}[/math] или [math]\mathrm{findMax}[/math] — поиск элемента с наибольшим приоритетом,
• [math]\mathrm{insert}[/math] или [math]\mathrm{push}[/math] — вставка нового элемента,
• [math]\mathrm{extractMin}[/math] или [math]\mathrm{extractMax}[/math] — извлечь элемент с наибольшим приоритетом,
• [math]\mathrm{deleteMin}[/math] или [math]\mathrm{deleteMax}[/math] — удалить элемент с наибольшим приоритетом,
• [math]\mathrm{increaseKey}[/math] или [math]\mathrm{decreaseKey}[/math] — обновить значение элемента,
• [math]\mathrm{merge}[/math] — объединение двух приоритетных очередей, сохраняя оригинальные очереди,
• [math]\mathrm{meld}[/math] — объединение двух приоритетных очередей, разрушая оригинальные очереди,
• [math]\mathrm{split}[/math] — разбить приоритную очередь на две части.

Реализации

Наивная

В качестве наивной реализации мы можем взять обычный список и при добавлении нового элемента класть его в конец, а при запросе элемента с максимальным приоритетом проходить по всему списку. Тогда операция [math]\mathrm{insert}[/math] будет выполняться за [math]O(1)[/math], а [math]\mathrm{extractMin}[/math] или [math]\mathrm{extractMax}[/math] за [math]O(n)[/math].

Обычная

Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за [math]O(\log n)[/math]. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.

Виды приоритетных очередей

Название	Операции				Описание
	[math]\mathrm{insert}[/math]	[math]\mathrm{extractMin}[/math]	[math]\mathrm{decreaseKey}[/math]	[math]\mathrm{merge}[/math]
Наивная реализация (неотсортированный список)	[math]O(1)[/math]	[math]O(n)[/math]	[math]O(n)[/math]	[math]O(1)[/math]	Наивная реализация с использованием списка.
Наивная реализация (отсортированный массив)	[math]O(n)[/math]	[math]O(1)[/math]	[math]O(\log n)[/math]	[math]O(n + m)[/math]	Наивная реализация с использованием отсортированного массива.
Двуродительская куча	[math]O(\sqrt{n})[/math]	[math]O(\sqrt{n})[/math]			Двуродительская куча (англ. bi-parental heap или beap) — такая куча, где у каждого элемента обычно есть два ребенка (если это не последний уровень) и два родителя (если это не первый уровень). Структура позволяет производить сублиненый поиск.
Двоичная куча	[math]O(\log n)[/math]	[math]O(\log n)[/math]	[math]O(\log n)[/math]	[math]O(n + m)[/math]	Двоичная куча (англ. binary heap) — такое двоичное дерево, для которого выполнены три условия: Значение в любой вершине не меньше, чем значения её потомков. Глубина листьев (расстояние до корня) отличается не более чем на 1 слой. Последний слой заполняется слева направо.
[math]d[/math]-арная куча	[math]O(\log_{d} n)[/math]	[math]O(d\log_{d} n)[/math]	[math]O(d\log_{d} n)[/math]	[math]O(n + m)[/math]	[math]d[/math]-арная куча (англ. [math]d[/math]-ary heap) — двоичная куча, в которой у каждого элемента [math]d[/math] детей вместо [math]2[/math].
Левосторонняя куча	[math]O(\log n)[/math]	[math]O(\log n)[/math]	[math]O(\log n)[/math]	[math]O(\log n)[/math]	Левосторонняя куча (англ. leftist heap) — двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи.
Биномиальная куча	[math]O(1)[/math]	[math]O(\log n)[/math]	[math]O(\log n)[/math]	[math]O(1)[/math]	Биномиальная куча (англ. binomial heap) — структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами: ключ каждой вершины не меньше ключа ее родителя все биномиальные деревья имеют разный размер
Спаренная куча	[math]O(1)[/math]	[math]O(\log n)[/math]	[math]O(\log n)[/math]	[math]O(1)[/math]	Спаренная куча (англ. pairing heap) — куча с относительно простой реализацией и хорошей производительностью, может быть рассмотрена как упрощенная Фибоначчиева куча.
Толстая куча	[math]O(1)[/math]	[math]O(\log n)[/math]	[math]O(1)[/math]	[math]O(\log n)[/math]	Толстая куча — это почти кучеобразный нагруженный лес.
2-3 куча	[math]O(1)[/math]	[math]O(\log n)[/math]	[math]O(1)[/math]	[math]O(1)[/math]	Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.
Тонкая куча	[math]O(1)[/math]	[math]O(\log n)[/math]	[math]O(1)[/math]	[math]O(1)[/math]	Тонкая куча (англ. thin heap) — это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и фибоначчиева куча, но имеющая большую практическую ценность из-за меньших констант.
Фибоначчиева куча	[math]O(1)[/math]	[math]O(\log n)[/math]	[math]O(1)[/math]	[math]O(1)[/math]	Куча, построенная на основе Фибоначчиева дерева. Фибоначчиево дерево (англ. Fibonacci tree) — биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
Куча Бродала-Окасаки	[math]O(1)[/math]	[math]O(\log n)[/math]	[math]O(1)[/math]	[math]O(1)[/math]	Куча Бродала-Окасаки (англ. Brodal's and Okasaki's Priority Queue) — основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping.

Применение

Приоритетные очереди используются в следующих алгоритмах: алгоритм Дейкстры, алгоритм Прима, дискретно-событийное моделирование (англ. discrete-event simulation, DES), алгоритм Хаффмана, поиск по первому наилучшему совпадению, управление полосой пропускания.

Реализации в языках программирования

• Стандартная библиотека шаблонов (англ. STL) в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
• Библиотека Boost для C++ включает в себя библиотеку для работу с кучами. В отличии от STL, поддерживает операции decrease-key и increase-key, а также имеет поддержку дополнительных видов куч, таких как фибоначчиева куча, биномиальная куча и спаренная куча.
• В Java 2 (начиная с версии 1.5) предоставляется реализация бинарной кучи в классе java.util.PriorityQueue<E>, который не поддерживает операции decrease-key и increase-key.
• Python имеет модуль heapq, который реализует очереди с приоритетами с помощью бинарной кучи.
• PHP имеет поддержку кучи на максимум SplMaxHeap и кучи на минимум SplMinHeap, как часть Standard PHP Library начиная с версии 5.3.
• В Perl имеются реализации бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.
• Go имеет пакет heap, в котором реализованы алгоритмы для работы с кучами.

См. также

• Сортировка
• Поисковые структуры данных
• Поиск подстроки в строке

Источники информации

• Wikidedia — Heap (data structure)
• Wikidedia — 2-3 heap
• Wikidedia — Beap
• Wikidedia — Binary heap
• Wikidedia — Binomial heap
• Wikidedia — Brodal queue
• Wikidedia — [math]d[/math]-ary heap
• Wikidedia — Fibonacci heap