Изменения

'''Приоритетная очередь''' (англ. ''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{meld}</tex> {{---}} объединение двух приоритетных очередей, разрушая оригинальные очереди, * <tex>\mathrm{split}</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%" | find-min<tex>\mathrm{insert}</tex>| align="center" width="5%" | insert<tex>\mathrm{extractMin}</tex>| align="center" width="5%" | delete-min<tex>\mathrm{decreaseKey}</tex>| align="center" | <tex>\mathrm{merge}</tex>

| [[2-3 куча]]| align="center" rowspan="11" | <tex>OНаивная реализация (1неотсортированный список)</tex>

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

| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 деревоНаивная реализация с использованием списка.

| [[Биномиальная куча]]Наивная реализация (отсортированный массив)| align="center" | <tex>O(n)</tex>

| align="center" | <tex>O(1n + m)</tex>| [[Биномиальная куча]] (англНаивная реализация с использованием отсортированного массива. ''binomial heap'') {{---}} структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами:* ключ каждой вершины не меньше ключа ее родителя * все биномиальные деревья имеют разный размер

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

| align="center" | <tex>O(m \logn)</tex>| align="center" | <tex>O(n+m))</tex>

| align="center" | <tex>O(\log log_{d} n )</ tex>| align="center" | <tex>O(d\log log_{d} n)</tex>| align="center" | <tex>O(d\log log_{d} n / \log d)</tex>| align="center" | <tex>O(m \log(n+m) / \log d)</tex>

| [[Фибоначчиева Сонная куча]]

* Алгоритм Приоритетные очереди используются в следующих алгоритмах: [[алгоритм Дейкстры* Алгоритм ]], [[алгоритм Прима* Дискретно]], дискретно-событийное моделирование (англ. ''discrete-event simulation, DES'')* Код <ref>[http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE-%D1%81%D0%BE%D0%B1%D1%8B%D1%82%D0%B8%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Wikipedia {{---}} Дискретно-событийное моделирование]</ref>, [[алгоритм Хаффмана* Поиск ]], поиск по первому наилучшему совпадению* Управление , управление полосой пропускания.

* Стандартная библиотека шаблонов <ref>[http://en.cppreference.com/w/cpp/container C++ {{---}} Стандартная библиотека шаблонов]</ref> (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.* Библиотека Boost <ref>[http://www.boost.org/ C++ {{---}} Boost]</ref> для C++ включает в себя библиотеку для работу с кучами. В отличии от STL, поддерживает операции decrease-key и increase-key, а также имеет поддержку дополнительных видов куч, таких как [[Фибоначчиева фибоначчиева куча]], [[Биномиальная биномиальная куча]] и [[Спаренная спаренная куча]].* В Java 2 (начиная с версии 1.5) предоставляется реализация бинарной кучи в классе java.util.PriorityQueue<E><ref>[http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html Java {{---}} java.util.PriorityQueue<E>]</ref>, который не поддерживает операции decrease-key и increase-key.* Python имеет модуль heapq<ref>[http://docs.python.org/2/library/heapq.html Python {{---}} heapq]</ref>, который реализует очереди с приоритетами с помощью бинарной кучи.* PHP имеет поддержку кучи на максимум (SplMaxHeap) <ref>[http://php.net/manual/ru/class.splmaxheap.php PHP {{---}} SplMaxHeap]</ref> и кучи на минимум (SplMinHeap)<ref>[http://php.net/manual/ru/class.splminheap.php PHP {{---}} SplMinHeap]</ref>, как часть Standard PHP Library начиная с версии 5.3.* В Perl имеются реализации <ref>[http://metacpan.org/pod/Heap Perl {{---}} Heap]</ref> бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.* Go имеет пакет heap<ref>[http://golang.org/pkg/container/heap/ Go {{---}} package heap]</ref>, в котором реализованы алгоритмы для работы с кучами.==См. также==*[[:Сортировка|Сортировка]]*[[:Поисковые структуры данных|Поисковые структуры данных]]*[[:Поиск подстроки в строке|Поиск подстроки в строке]]==Примечания==

* [http://en.wikipedia.org/wiki/Heap_(data_structure)| Wikidedia Wikipedia {{---}} Heap (data structure)]* [http://en.wikipedia.org/wiki/2%E2%80%933_heap| Wikidedia Wikipedia {{---}} 2-3 heap]* [http://en.wikipedia.org/wiki/Beap| Wikidedia Wikipedia {{---}} Beap]* [http://en.wikipedia.org/wiki/Binary_heap| Wikidedia Wikipedia {{---}} Binary heap]* [http://en.wikipedia.org/wiki/Binomial_heap| Wikidedia Wikipedia {{---}} Binomial heap]* [http://en.wikipedia.org/wiki/Brodal_queue| Wikidedia Wikipedia {{---}} Brodal queue]* [http://en.wikipedia.org/wiki/D-ary_heap| Wikidedia Wikipedia {{---}} <tex>d</tex>-ary heap]* [http://en.wikipedia.org/wiki/Fibonacci_heap| Wikidedia Wikipedia {{---}} Fibonacci heap]