Изменения

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

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

* find-min (find-max) - поиск элемента с наибольшим приоритетом

* insert (push) - вставка нового элемента

* delete-min (delete-max) - удалить элемент с наибольшим приоритетом

* merge - объединение двух приоритетных очередей

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

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

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

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

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

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

{| class="wikitable"

|-

|-

|}

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

* Алгоритм Дейкстры

* Поиск по первому наилучшему совпадению

* Управление полосой пропускания

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

* Стандартная библиотека шаблонов (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.

* В Perl имеются реализации бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.

* Go имеет пакет heap, в котором реализованы алгоритмы для работы с кучами.

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

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