Изменения

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

 * find<tex>\mathrm{findMin}</tex> или <tex>\mathrm{findMax}</tex> {{-min (find-max) - }} поиск элемента с наибольшим приоритетом* <tex>\mathrm{insert (}</tex> или <tex>\mathrm{push) }</tex> {{--- }} вставка нового элемента* extract<tex>\mathrm{extractMin}</tex> или <tex>\mathrm{extractMax}</tex> {{-min (extract-max) - }} извлечь элемент с наибольшим приоритетом* delete<tex>\mathrm{deleteMin}</tex> или <tex>\mathrm{deleteMax}</tex> {{-min (delete-max) - }} удалить элемент с наибольшим приоритетом* <tex>\mathrm{increaseKey}</tex> или <tex>\mathrm{decreaseKey}</tex> {{---}} обновить значение элемента* <tex>\mathrm{merge }</tex> {{-- -}} объединение двух приоритетных очередей 

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

| align="center" width="5%" | delete-minextractMin| align="center" width="5%" | decreaseKey

| [[Куча БродалаСпаренная куча]]| align="center" | <tex>O(1)</tex>| align="center" | <tex>O(\log n)</tex>| align="center" | <tex>O(\log n)</tex>| align="center" | <tex>O(1)</tex>| [[Спаренная куча]] (англ. ''pairing heap'') {{-Окасаки--}} куча с относительно простой реализацией и хорошей производительностью, может быть рассмотрена как упрощенная [[Фибоначчиева куча]].|-| [[Толстая куча]]

| align="center" | <tex>O(\log n)</tex>| [[Куча Бродала-ОкасакиТолстая куча]] (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrappingэто почти кучеобразный нагруженный лес.

| [[Спаренная d-арная куча| <tex>d</tex>-арная куча]]| align="center" | <tex>O(1\log_{d} n)</tex>| align="center" | <tex>O(d\log log_{d} n)</tex>| align="center" | <tex>O(1\log_{d} n)</tex>| align="center" | <tex>O(m \log_{d}(n+m))</tex>| [[Спаренная d-арная куча| <tex>d</tex>-арная куча]] (англ. ''pairing <tex>d</tex>-ary heap'') {{---}} куча с относительно простой реализацией и хорошей производительностью, может быть рассмотрена как упрощенная [[Фибоначчиева двоичная куча]], в которой у каждого элемента <tex>d</tex> детей вместо <tex>2</tex>.

| [[Толстая Двуродительская куча]]| align="center" | <tex>O(1\sqrt{n})</tex>| align="center" | <tex>O(\log sqrt{n})</tex>| align="center" | <tex>O(\log n)</tex>| || [[Толстая Двуродительская куча]] (англ. ''bi-parental heap'' или ''beap'') {{---}} такая куча, где у каждого элемента обычно есть два ребенка (если это не последний уровень) и два родителя (если это почти кучеобразный нагруженный лесне первый уровень). Структура позволяет производить сублиненый поиск.

| [[Тонкая куча]]Наивная реализация

| align="center" | <tex>O(\log n)</tex>| align="center" | <tex>O(n)</tex>

| [[Тонкая куча]] (англ. ''thin heap'') {{---}} это структура данных, реализующая приоритетную очередь Наивная реализация с теми же асимптотическими оценками, что и [[фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.|-| [[Фибоначчиева куча]]| align="center" | <tex>O(1)</tex>| align="center" | <tex>O(\log n)</tex>| align="center" | <tex>O(1)</tex>| Куча, построенная на основе Фибоначчиева дерева. [[Фибоначчиево дерево]] (англ. ''Fibonacci tree'') {{---}} биномиальное дерево, где у каждой вершины удалено не более одного ребенкаиспользованием списка.

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

* [http://en.cppreference.com/w/cpp/container Стандартная библиотека шаблонов ] (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.* Библиотека [http://www.boost.org/ Boost ] для C++ включает в себя библиотеку для работу с кучами. В отличии от [http://en.cppreference.com/w/cpp/container STL], поддерживает операции decrease-key и increase-key, а также имеет поддержку дополнительных видов куч, таких как [[Фибоначчиева фибоначчиева куча]], [[Биномиальная биномиальная куча]] и [[Спаренная спаренная куча]].* В Java 2 (начиная с версии 1.5) предоставляется реализация бинарной кучи в классе [http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html java.util.PriorityQueue<E>], который не поддерживает операции decrease-key и increase-key.* Python имеет модуль [http://docs.python.org/2/library/heapq.html heapq], который реализует очереди с приоритетами с помощью бинарной кучи.* PHP имеет поддержку кучи на максимум ([http://php.net/manual/ru/class.splmaxheap.php SplMaxHeap) ] и кучи на минимум ([http://php.net/manual/ru/class.splminheap.php SplMinHeap)], как часть Standard PHP Library начиная с версии 5.3.* В 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/2%E2%80%933_heap| Wikidedia {{---}} 2-3 heap]* [http://en.wikipedia.org/wiki/Beap| Wikidedia {{---}} Beap]* [http://en.wikipedia.org/wiki/Binary_heap| Wikidedia {{---}} Binary heap]* [http://en.wikipedia.org/wiki/Binomial_heap| Wikidedia {{---}} Binomial heap]* [http://en.wikipedia.org/wiki/Brodal_queue| Wikidedia {{---}} Brodal queue]* [http://en.wikipedia.org/wiki/D-ary_heap| Wikidedia {{---}} <tex>d</tex>-ary heap]* [http://en.wikipedia.org/wiki/Fibonacci_heap| Wikidedia {{---}} Fibonacci heap]