Изменения

'''Приоритетная очередь''' (англ. 'Поисковая структура данных'priority queue'') {{---}} это абстрактная любая структура данных на подобии стека или очередиреализующая эффективный поиск конкретных элементов множества, например, где у каждого элемента есть приоритетконкретной записи в базе данных. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом Простейшей, наиболее общей, но менее эффективной поисковой структурой является простая неупорядоченная последовательная всех элементов. Если у элементов одинаковые приоритетыРасположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, они распологаются а также в зависимости от своей позиции средней случае. Используемые в очередиреальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур пропорциональна <tex>n</tex>, их построение окупится, даже если поступает лишь несколько запросов. === Тип === '''Статические поисковые структуры данных''' (англ. Обычно приоритетные очереди реализуются с помощью куч ''Offline search structures'') предназначены для ответа на запросы на фиксированной базе данных. '''Динамические поисковые структуры''' (англ. ''heapOnline search structures'')также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных. Любую динамическую структуру данных можно сделать статической, если запретить вставку и удаление.Также если множество ключей известно, то можно его заранее упорядочить так, чтобы избежать худших случаев в поисках в структурах данных. ==Операции= Время работы ===* find-min (find-max) - поиск элемента с наибольшим приоритетом* insert (push) Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время {{- вставка нового элемента* extract-min (extract-max) }} минимальное время работы алгоритма на каком- извлечь элемент с наибольшим приоритетом* deleteлибо наборе. Худшее время {{-min (delete-max) - удалить элемент с наибольшим приоритетом}} наибольшее время.* merge - объединение двух приоритетных очередей==Реализации=Используемая память === Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты составляют <tex>O(n)</tex>. ===НаивнаяСравнение структур данных ===В качестве наивной Сравним эффективность поисковых структур данных для реализации мы можем взять обычный список интерфейса [[Упорядоченное множество|упорядоченного множества]]. Время работы методов <tex>Predecessor</tex> и при добавлении нового элемента класть его в конец, а при запросе элемента с максимальным приоритетом проходить по всему списку. Тогда операция insert будет выполняться за <tex>O(1)Successor</tex>, а extract-max (extract-min) за совпадает с временем работы <tex>O(n)Search</tex>.===Обычная===Для лучшей производительности приоритетные очереди реализуют <tex>n</tex> {{---}} количество хранимых чисел, каждое из которых представляется с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)w</tex>. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операцийбитов.==Виды приорететных очередей==

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

! style="background: #ddffdd;" | alignСреднее! style="centerbackground: #ffdddd;" width| Худшее! style="5%background: #ddffdd;" | find-minСреднее! style="background: #ffdddd;" | alignХудшее! style="centerbackground: #ddffdd;" | insertСреднее| align! style="centerbackground: #ffdddd;" width| Худшее! style="5%background: #ddffdd;" | delete-minСреднее| align! style="centerbackground: #ffdddd;" | mergeХудшее

| [[2-3 куча]]| align="center" rowspan="11" | <tex>O(1)</tex>| align="center" | <tex>O(1)</tex>!| align! colspan="center9" | <tex>O(\log n)</tex>| align="center" | <tex>O(1)</tex>| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево. Динамические структуры данных

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

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

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

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

| [[d-арная кучаДерево поиска, наивная реализация]]| align="center" style="background: #ffffdd;" | <tex>dO(\log n)</tex>-арная куча]]| align="center" style="background: #ffdddd;" | <tex>O(\log n )</ tex>| align="center" style="background: #ffffdd;" | <tex>O(\log dn)</tex>| align="center" style="background: #ffdddd;" | <tex>O(d\log n / \log d)</tex>| align="center" style="background: #ffffdd;" | <tex>O(m \log(n+m) </ \log dtex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| [[d-арная кучаcolspan="2" align="center" style="background: #ffffdd;" | <tex>dO(n)</tex>-арная куча]] (англ. ''| align="center" | Бинарное дерево поиска обладает следующим свойством: если <tex>dx</tex>-ary heap'') {{---}} [[двоичная куча]]узел бинарного дерева с ключом <tex>k</tex>, то все узлы в которой у каждого элемента левом поддереве должны иметь ключи, меньшие <tex>dk</tex> детей вместо , а в правом поддереве большие <tex>2k</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>| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| [[Левосторонняя куча]] align="center" style="background: #ffdddd;" | <tex>O(англ. ''leftist heap''n) {{---}} двоичное левосторонее дерево </tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(не обязательно сбалансированноеn)</tex>| align="center" | Вариант [[Дерево поиска, но наивная реализация|двоичного дерево поиска]] с соблюдением порядка кучидобавлением инвариата "случайности", что уменьнашает ожидаемую высоту дерева.

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

| [[Толстая куча2-3 дерево]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(1\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" | Структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[Толстая кучаB-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]] {{---}} это почти кучеобразный нагруженный лес.

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

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

 ==Применение==* Алгоритм Дейкстры* Алгоритм Прима* Дискретно-событийное моделирование (англСм. ''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://en.wikipedia.org/wiki/Binomial_heapSearch_data_structure| Wikidedia {{---}} Binomial heapSearch data structure]* [http://en.wikipedia.org/wiki/Brodal_queue| Wikidedia {{---}} Brodal queue]* [http://enhabrahabr.wikipedia.org/wiki/D-ary_heap| Wikidedia {{---}} <tex>d<ru/tex>-ary heap]* [http:post/188010/en.wikipedia.org/wiki/Fibonacci_heap| Wikidedia Habrahabr {{---}} Fibonacci heapЗнай сложности алгоритмов ]

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