Изменения

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

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

'''Динамические поисковые структуры''' ===Обычная===Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(англ. ''Offline search structures''\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="24" | 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" stylewidth="background: #ffdddd;5%" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>| align="center" | Наивная реализация, использующая [[Динамический массив|динамический массив]]. Добавление происходит в конец массива, а для поиска элемента просто проходим по всему массиву.|find-min| Отсортированный массив| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>insert| colspan="2" align="center" stylewidth="background: #ffdddd;5%" | <tex>O(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" | То же самое, но теперь массив отсортирован. Поиск ускоряется за счёт возможности применить [[Целочисленный двоичный поиск|двоичный поиск]]. Вставка замедляется из-за необходимости поддерживать инвариант отсортированности.|delete-min| Неотсортированный [[Список|список]]| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>| colspan="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.merge

| Отсортированный [[Список|список2-3 куча]]| colspan="2" align="center" stylerowspan="background: #ffdddd;11" | <tex>O(n1)</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(n1)</tex>| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.

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

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

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

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

| [[Список с пропускамиФибоначчиева куча]]| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n1)</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 n1)</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англ. ''Fibonacci tree'')</tex>{{---}} биномиальное дерево, где у каждой вершины удалено не более одного ребенка. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до <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_heap| Wikidedia {{---}} Binary heap]* [http:Search_data_structure//en.wikipedia.org/wiki/Binomial_heap|Wikidedia {{---}} Search data structureBinomial heap]* [http://en.wikipedia.org/wiki/Brodal_queue| Wikidedia {{---}} Brodal queue]* [http://habrahabren.ruwikipedia.org/wiki/D-ary_heap| Wikidedia {{---}} <tex>d</posttex>-ary heap]* [http:/188010/ Habrahabr en.wikipedia.org/wiki/Fibonacci_heap| Wikidedia {{---}} Знай сложности алгоритмов Fibonacci heap]

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