Изменения

Приоритетные очереди поддерживают следующие операции: * <tex>\mathrm{findMin}</tex> или <tex>\mathrm{findMax}</tex> {{---}} поиск элемента с наибольшим приоритетом, * <tex>\mathrm{insert}</tex> или <tex>\mathrm{push}</tex> {{---}} вставка нового элемента, * <tex>\mathrm{extractMin}</tex> или <tex>\mathrm{extractMax}</tex> {{---}} извлечь элемент с наибольшим приоритетом, * <tex>\mathrm{deleteMin}</tex> или <tex>\mathrm{deleteMax}</tex> {{---}} удалить элемент с наибольшим приоритетом, * <tex>\mathrm{increaseKey}</tex> или <tex>\mathrm{decreaseKey}</tex> {{---}} обновить значение элемента, * <tex>\mathrm{merge}</tex> {{---}} объединение двух приоритетных очередей, сохраняя оригинальные очереди, * <tex>\mathrm{meld}</tex> {{---}} объединение двух приоритетных очередей, разрушая оригинальные очереди, * <tex>\mathrm{split}</tex> {{---}} разбить приоритную очередь на две части.

| [[2-3 куча]]Наивная реализация (неотсортированный список)

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

| align="center" | <tex>O(1)</tex>| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 деревоНаивная реализация с использованием списка.

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

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

| [[Фибоначчиева Двоичная куча]]| align="center" | <tex>O(1\log n)</tex>| align="center" | <tex>O(\log n)</tex>

| align="center" | <tex>O(n + m)</tex>| [[Двоичная куча]] (англ. ''binary heap'') {{---}} такое двоичное дерево, для которого выполнены три условия:*Значение в любой вершине не меньше, чем значения её потомков.*Глубина листьев (расстояние до корня) отличается не более чем на 1слой.*Последний слой заполняется слева направо.|-| [[d-арная куча| <tex>d</tex>-арная куча]]| align="center" | <tex>O(\log_{d} n)</tex>| align="center" | <tex>O(1d\log_{d} n)</tex>| align="center" | <tex>O(d\log_{d} n)</tex>| align="center" | <tex>O(n + m)</tex>| Куча, построенная на основе Фибоначчиева дерева. [[Фибоначчиево деревоd-арная куча| <tex>d</tex>-арная куча]] (англ. ''Fibonacci tree<tex>d</tex>-ary heap'') {{---}} биномиальное дерево[[двоичная куча]], где в которой у каждой вершины удалено не более одного ребенкакаждого элемента <tex>d</tex> детей вместо <tex>2</tex>.

| [[Куча Бродала-ОкасакиЛевосторонняя куча]]| align="center" | <tex>O(1\log n)</tex>| align="center" | <tex>O(\log n)</tex>| align="center" | <tex>O(\log n)</tex>

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

| [[Двоичная 2-3 куча]]| align="center" | <tex>O(1)</tex>

| align="center" | <tex>O(m \log1)</tex>| align="center" | <tex>O(n+m)1)</tex>| Куча, построенная на основе Фибоначчиева дерева. [[Двоичная кучаФибоначчиево дерево]] (англ. ''binary heapFibonacci tree'') {{---}} такое двоичное биномиальное дерево, для которого выполнены три условия:*Значение в любой вершине не меньше, чем значения её потомков.*Глубина листьев (расстояние до корня) отличается где у каждой вершины удалено не более чем на 1 слой.*Последний слой заполняется слева направоодного ребенка.

| [[Левосторонняя кучаКуча Бродала-Окасаки]]| align="center" | <tex>O(\log n)</tex>| align="center" | <tex>O(\log n1)</tex>

| Наивная реализация с использованием списка[[Куча Бродала-Окасаки]] (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping.

Приоритетные очереди используются в следующих алгоритмах: [[алгоритм Дейкстры]], [[алгоритм Прима]], дискретно-событийное моделирование (англ. ''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++ включает в себя библиотеку для работу с кучами. В отличии от [http://en.cppreference.com/w/cpp/container 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>, в котором реализованы алгоритмы для работы с кучами.