Изменения

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

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

===Обычная===Для лучшей производительности приоритетные очереди реализуют с помощью куч'''Динамические поисковые структуры''' (англ. ''Offline search structures'') также позволяют вставки, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)</tex>или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных. Использование специальных кучЛюбую динамическую структуру данных можно сделать статической, таких как Фибоначчиева куча если запретить вставку и спаренная кучаудаление. Также если множество ключей известно, то можно его заранее упорядочить так, позволяет еще больше улучшить асимптотику некоторый операцийчтобы избежать худших случаев в поисках в структурах данных.

==Виды приорететных очередей=Время работы === Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время {{---}} минимальное время работы алгоритма на каком-либо наборе. Худшее время {{---}} наибольшее время. === Используемая память === Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты составляют <tex>O(n)</tex>. === Сравнение структур данных === Сравним эффективность поисковых структур данных для реализации интерфейса [[Упорядоченное множество|упорядоченного множества]]. Время работы методов <tex>Predecessor</tex> и <tex>Successor</tex> совпадает с временем работы <tex>Search</tex>. <tex>n</tex> {{---}} количество хранимых чисел, каждое из которых представляется с помощью <tex>w</tex> битов.

! rowspan="2" | Название! colspan="42" | ОперацииInsert! colspan="2" | Delete! colspan="2" | Search! colspan="2" | Память

! style="background: #ddffdd;" | Среднее! style="background: #ffdddd;" | Худшее! style="background: #ddffdd;" | Среднее! style="background: #ffdddd;" | Худшее! style="background: #ddffdd;" | Среднее! style="background: #ffdddd;" | Худшее! style="background: #ddffdd;" | Среднее! style="background: #ffdddd;" | Худшее|-!! colspan="9" align="center" | Динамические структуры данных|-| Неотсортированный массив| align="center" style="background: #ddffdd;" | <tex>O(1)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| align="center" style="background: #ddffdd;" | <tex>O(1)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" widthstyle="5%background: #ffdddd;" | find<tex>O(n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>| align="center" | Наивная реализация, использующая [[Динамический массив|динамический массив]]. Добавление происходит в конец массива, а для поиска элемента просто проходим по всему массиву.|-min| Отсортированный массив| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | insert<tex>O(\log n)</tex>| colspan="2" align="center" widthstyle="5%background: #ffffdd;" | delete<tex>O(n)</tex>| align="center" | То же самое, но теперь массив отсортирован. Поиск ускоряется за счёт возможности применить [[Целочисленный двоичный поиск|двоичный поиск]]. Вставка замедляется из-за необходимости поддерживать инвариант отсортированности.|-min| Неотсортированный [[Список|список]]| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>| mergecolspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>| align="center" rowspan="2" | Аналогично массиву, но храним данные в [[Список|списке]]. Можно хранить дополнительную информацию о вершинах, что позволит ускорить время работы операции delete.

| Отсортированный [[2-3 кучаСписок|список]]| colspan="2" align="center" rowspanstyle="11background: #ffdddd;" | <tex>O(1n)</tex>| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(1n)</tex>| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.

| [[Биномиальная кучаДерево поиска, наивная реализация]]| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(1n)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| align="center" style="background: #ffffdd;" | <tex>O(1\log n)</tex>| [[Биномиальная куча]] align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(англ. ''binomial heap''n) </tex>| align="center" | Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> {{---}} структура данныхузел бинарного дерева с ключом <tex>k</tex>, реализующая приоритетную очередьто все узлы в левом поддереве должны иметь ключи, которая представляет собой набор биномиальных деревьев с двумя свойствами:* ключ каждой вершины не меньше ключа ее родителя * все биномиальные деревья имеют разный размерменьшие <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.

| [[Куча Бродала-ОкасакиРандомизированное бинарное дерево поиска]]| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(1n)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(1n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>| align="center" | Вариант [[Куча Бродала-ОкасакиДерево поиска, наивная реализация|двоисного дерево поиска]] (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании биномиальной кучи без каскадных ссылокс добавлением инвариата "случайности", добавлении минимального элемента и на идеи Data-structural bootstrappingчто уменьнашает ожидаемую высоту дерева.

| [[Двоичная кучаАВЛ-дерево]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(m \logn)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n+m))</tex>| align="center" | Сбалансированное [[Двоичная кучаДерево поиска, наивная реализация|двоичное дерево поиска]] (англ. ''binary heap'') {{---}} такое двоичное дерево, в котором поддерживается следующее свойство: для которого выполнены три условия:*Значение в любой вершине не меньше, чем значения каждой его вершины высота её потомков.*Глубина листьев (расстояние до корня) отличается двух поддеревьев различается не более чем на <tex>1 слой.*Последний слой заполняется слева направо</tex>.

| [[Двуродительская куча2-3 дерево]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\sqrt{log n})</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\sqrt{log n})</tex>| colspan="2" align="center" style="background: #ffffdd;" |<tex>O(\log n)</tex>| [[Двуродительская куча]] colspan="2" align="center" style="background: #ffffdd;" | <tex>O(англ. ''bi-parental heap'' или ''beap''n) {{---}} такая куча</tex>| align="center" | Структура данных, представляющая собой сбалансированное дерево поиска, где у такое что из каждого элемента обычно есть два ребенка (если это не последний уровень) узла может выходить две или три ветви и два родителя (если это не первый уровень)глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0. Структура позволяет производить сублиненый поискBE|B+ дерева]].

| [[dB-арная кучадерево]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>dO(\log n)</tex>-арная куча]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n / \log d)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(d\log n / \log d)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(m \log(n+m) / \log d)</tex>| [[d-арная кучаalign="center" | Cильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>dO(\log n)</tex>. B-арная куча]] (англ. ''дерево с <tex>dn</tex>-ary heap'') {{---}} [[двоичная куча]], в которой у каждого элемента узлами имеет высоту <tex>dO(\log n)</tex> . Количество детей вместо узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>2O(\log n)</tex>.

| [[Левосторонняя кучаКрасно-черное дерево]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>| align="center" | Сбалансированное [[Левосторонняя кучаДерево поиска, наивная реализация|двоичное дерево поиска]] , в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. ''leftist heapred'') {{---}} двоичное левосторонее дерево и "чёрный" (англ. ''black''). При этом все листья дерева являются фиктивными и не обязательно сбалансированное)содержат данных, но с соблюдением порядка кучиотносятся к дереву и являются чёрными.

| [[Спаренная кучаДекартово дерево]]| align="center" style="background: #ffffdd;" | <tex>O(1\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(1n)</tex>| [[Спаренная куча]] align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>| align="center" | Бинарное дерево, в узлах которого хранится пары <tex> (англ. ''pairing heap''x,y) </tex>, где <tex>x</tex> {{---}} куча с относительно простой реализацией это ключ, а <tex>y</tex> {{---}} это приоритет. Также оно является [[Дерево поиска, наивная реализация|двоичным деревом поиска]] по <tex>x</tex> и хорошей производительностью, может быть рассмотрена как упрощенная [[Фибоначчиева Двоичная куча|пирамидой]]по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.

| [[Толстая кучаSplay-дерево]]| align="center" style="background: #ffffdd;" | <tex>O(1\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>| align="center" | [[Толстая кучаДерево поиска, наивная реализация|Двоичное дерево поиска]] {{--. Оно позволяет находить быстрее те данные, которые использовались недавно, за счёт '''перемещения к корню''' (англ. ''Move to root''). Относится к разряду сливаемых деревьев. Сплей-}} это почти кучеобразный нагруженный лесдерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.

| [[Тонкая кучаДерево ван Эмде Боаса]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(1\log w)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log nw)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(12^w)</tex>| align="center" | Cтруктура данных, представляющая собой [[Тонкая кучаДерево поиска, наивная реализация|дерево поиска]] , позволяющее хранить целые неотрицательные числа в интервале <tex>[0;2^w)</tex> и осуществлять над ними все соответствующие дереву поиска операции. Проще говоря, данная структура позволяет хранить <tex>w</tex>-битные числа.Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log w)</tex>, что асимптотически лучше, чем <tex>O(англ. ''thin heap''\log n) </tex> в большинстве других деревьев поиска, где <tex>n</tex> {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших константколичество элементов в дереве.

| [[Фибоначчиева кучаСписок с пропусками]]| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(1n)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| align="center" style="background: #ffffdd;" | <tex>O(1\log n)</tex>| Кучаalign="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex> | align="center" | Вероятностная структура данных, построенная основанная на основе Фибоначчиева дереванескольких отсортированных односвязных списках. [[Фибоначчиево дерево]] Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(англn)</tex>. ''Fibonacci tree''Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до <tex>\Theta(\log(n)) {{---}} биномиальное дерево, где у каждой вершины удалено не более одного ребенка.</tex>

==Применение==* Алгоритм Дейкстры* Алгоритм Прима* Дискретно-событийное моделирование (англСм. ''discrete-event simulation, DES'')* Код Хаффмана* Поиск по первому наилучшему совпадению* Управление полосой пропускания ==Реализации в языках программированиятакже==* Стандартная библиотека шаблонов (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.* Библиотека Boost для C++ включает в себя библиотеку для работу с кучами. В отличии от STL, поддерживает операции decrease-key и increase-key, а также имеет поддержку дополнительных видов куч, таких как [[Фибоначчиева куча]], [[Биномиальная куча]] и [[Спаренная куча]].* В Java 2 (начиная с версии 1.5) предоставляется реализация бинарной кучи в классе java.util.PriorityQueue<E>, который не поддерживает операции decrease-key и increase-key.* Python имеет модуль heapq, который реализует очереди с приоритетами с помощью бинарной кучи.* PHP имеет поддержку кучи на максимум (SplMaxHeap) и кучи на минимум (SplMinHeap), как часть Standard PHP Library начиная с версии 5.3.* В Perl имеются реализации бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.* Go имеет пакет 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_heapSearch_data_structure| Wikidedia {{---}} Binary heapSearch data structure]* [http://en.wikipedia.org/wiki/Binomial_heap| Wikidedia {{---}} Binomial heap]* [http://en.wikipediahabrahabr.orgru/wikipost/Brodal_queue| Wikidedia {{---}} Brodal queue]* [http://en.wikipedia.org/wiki/D-ary_heap| Wikidedia {{---}} <tex>d</tex>-ary heap]* [http:188010//en.wikipedia.org/wiki/Fibonacci_heap| Wikidedia Habrahabr {{---}} Fibonacci heapЗнай сложности алгоритмов ]

[[Категория: Приоритетные очередиДеревья поиска]]