Изменения

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

==Операции==

* <tex>\mathrm{findMin}</tex> или <tex>\mathrm{findMax}</tex> {{---}} поиск элемента с наибольшим приоритетом

* <tex>\mathrm{insert}</tex> или <tex>\mathrm{push}</tex> {{---}} вставка нового элемента

* <tex>\mathrm{increaseKey}</tex> или <tex>\mathrm{decreaseKey}</tex> {{---}} обновить значение элемента

* <tex>\mathrm{merge}</tex> {{---}} объединение двух приоритетных очередей

==Реализации==

===Наивная===

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

===Обычная===

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

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

{| class="wikitable"

|-

|-

|}

==Применение==

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

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

* [http://en.cppreference.com/w/cpp/container Стандартная библиотека шаблонов] (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.

* В Perl имеются [http://metacpan.org/pod/Heap реализации] бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.

* Go имеет пакет [http://golang.org/pkg/container/heap/ heap], в котором реализованы алгоритмы для работы с кучами.

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

* [http://en.wikipedia.org/wiki/Heap_(data_structure) Wikidedia {{---}} Heap (data structure)]

* [http://en.wikipedia.org/wiki/D-ary_heap Wikidedia {{---}} <tex>d</tex>-ary heap]

* [http://en.wikipedia.org/wiki/Fibonacci_heap Wikidedia {{---}} Fibonacci heap]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Приоритетные очереди]]

[[Категория: Структуры данных]]