Поисковые структуры данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 5 участников)
Строка 1: Строка 1:
'''Приоритетная очередь''' (англ. ''priority queue'') {{---}} это абстрактная структура данных на подобии стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они распологаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью куч (англ. ''heap'').
+
'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.
==Операции==
+
 
* find-min (find-max) - поиск элемента с наибольшим приоритетом
+
Простейшей, наиболее общей, но менее эффективной поисковой структурой является простая неупорядоченная последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур пропорциональна <tex>n</tex>, их построение окупится, даже если поступает лишь несколько запросов.
* insert (push) - вставка нового элемента
+
 
* extract-min (extract-max) - извлечь элемент с наибольшим приоритетом
+
=== Тип ===
* delete-min (delete-max) - удалить элемент с наибольшим приоритетом
+
 
* merge - объединение двух приоритетных очередей
+
'''Статические поисковые структуры данных''' (англ. ''Offline search structures'') предназначены для ответа на запросы на фиксированной базе данных.
==Реализации==
+
 
===Наивная===
+
'''Динамические поисковые структуры''' (англ. ''Online search structures'') также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных. Любую динамическую структуру данных можно сделать статической, если запретить вставку и удаление. Также если множество ключей известно, то можно его заранее упорядочить так, чтобы избежать худших случаев в поисках в структурах данных.
В качестве наивной реализации мы можем взять обычный список и при добавлении нового элемента класть его в конец, а при запросе элемента с максимальным приоритетом проходить по всему списку. Тогда операция insert будет выполняться за <tex>O(1)</tex>, а extract-max (extract-min) за <tex>O(n)</tex>.
+
 
===Обычная===
+
=== Время работы ===
Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)</tex>. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.
+
 
==Виды приорететных очередей==
+
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время {{---}} минимальное время работы алгоритма на каком-либо наборе. Худшее время {{---}} наибольшее время.
 +
 
 +
=== Используемая память ===
 +
 
 +
Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты составляют <tex>O(n)</tex>.
 +
 
 +
=== Сравнение структур данных ===
 +
 
 +
Сравним эффективность поисковых структур данных для реализации интерфейса [[Упорядоченное множество|упорядоченного множества]]. Время работы методов <tex>Predecessor</tex> и <tex>Successor</tex> совпадает с временем работы <tex>Search</tex>.
 +
 
 +
<tex>n</tex> {{---}} количество хранимых чисел, каждое из которых представляется с помощью <tex>w</tex> битов.
 +
 
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
! rowspan="2" | Название
+
! rowspan="2" |
! colspan="4" | Операции
+
! colspan="2" | Insert
 +
! colspan="2" | Delete
 +
! colspan="2" | Search
 +
! colspan="2" | Память
 
! rowspan="2" | Описание
 
! rowspan="2" | Описание
 
|-
 
|-
| align="center" width="5%" | find-min
+
! style="background: #ddffdd;" | Среднее
| align="center" | insert
+
! style="background: #ffdddd;" | Худшее
| align="center" width="5%" | delete-min
+
! style="background: #ddffdd;" | Среднее
| align="center" | merge
+
! style="background: #ffdddd;" | Худшее
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 
|-
 
|-
| [[2-3 куча]]
+
!
| align="center" rowspan="11" | <tex>O(1)</tex>
+
! colspan="9" align="center" | Динамические структуры данных
| align="center" | <tex>O(1)</tex>
 
| align="center" | <tex>O(\log n)</tex>
 
| align="center" | <tex>O(1)</tex>
 
| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.
 
 
|-
 
|-
| [[Биномиальная куча]]
+
| Неотсортированный массив
| align="center" | <tex>O(1)</tex>
+
| align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| align="center" | <tex>O(1)</tex>
+
| align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| [[Биномиальная куча]] (англ. ''binomial heap'') {{---}} структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами:
+
| 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" | Наивная реализация, использующая [[Динамический массив|динамический массив]]. Добавление происходит в конец массива, а для поиска элемента просто проходим по всему массиву.
 
|-
 
|-
| [[Куча Бродала-Окасаки]]
+
| Отсортированный массив
| align="center" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| align="center" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| [[Куча Бродала-Окасаки]] (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping.
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | То же самое, но теперь массив отсортирован. Поиск ускоряется за счёт возможности применить [[Целочисленный двоичный поиск|двоичный поиск]]. Вставка замедляется из-за необходимости поддерживать инвариант отсортированности.
 
|-
 
|-
| [[Двоичная куча]]
+
| Неотсортированный [[Список|список]]
| align="center" | <tex>O(\log n)</tex>
+
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| align="center" | <tex>O(m \log(n+m))</tex>
+
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| [[Двоичная куча]] (англ. ''binary heap'') {{---}} такое двоичное дерево, для которого выполнены три условия:
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
*Значение в любой вершине не меньше, чем значения её потомков.
+
| align="center" rowspan="2" | Аналогично массиву, но храним данные в [[Список|списке]].
*Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
 
*Последний слой заполняется слева направо.
 
 
|-
 
|-
| [[Двуродительская куча]]
+
| Отсортированный [[Список|список]]
| align="center" | <tex>O(\sqrt{n})</tex>
+
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| align="center" | <tex>O(\sqrt{n})</tex>
+
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| |
+
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| [[Двуродительская куча]] (англ. ''bi-parental heap'' или ''beap'') {{---}} такая куча, где у каждого элемента обычно есть два ребенка (если это не последний уровень) и два родителя (если это не первый уровень). Структура позволяет производить сублиненый поиск.
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|-
 
|-
| [[d-арная куча| <tex>d</tex>-арная куча]]
+
| [[Дерево поиска, наивная реализация]]
| align="center" | <tex>O(\log n / \log d)</tex>
+
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <tex>O(d\log n / \log d)</tex>
+
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| align="center" | <tex>O(m \log(n+m) / \log d)</tex>
+
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| [[d-арная куча| <tex>d</tex>-арная куча]] (англ. ''<tex>d</tex>-ary heap'') {{---}} [[двоичная куча]], в которой у каждого элемента <tex>d</tex> детей вместо <tex>2</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" | Бинарное дерево поиска  обладает следующим свойством:  если <tex>x</tex> {{---}} узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие <tex>k</tex>,  а в правом поддереве большие <tex>k</tex>.
 
|-
 
|-
| [[Левосторонняя куча]]
+
| [[Рандомизированное бинарное дерево поиска]]
| align="center" | <tex>O(\log n)</tex>
+
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| [[Левосторонняя куча]] (англ. ''leftist heap'') {{---}} двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи.
+
| 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" | Вариант [[Дерево поиска, наивная реализация|двоичного дерево поиска]] с добавлением инвариата "случайности", что уменьнашает ожидаемую высоту дерева.
 
|-
 
|-
| [[Спаренная куча]]
+
|[[АВЛ-дерево]]
| align="center" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| [[Спаренная куча]] (англ. ''pairing heap'') {{---}} куча с относительно простой реализацией и хорошей производительностью, может быть рассмотрена как упрощенная [[Фибоначчиева куча]].
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на <tex>1</tex>.
 
|-
 
|-
| [[Толстая куча]]
+
|[[2-3 дерево]]
| align="center" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <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-дерево]]
| align="center" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| [[Тонкая куча]] (англ. ''thin heap'') {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Cильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>
 
|-
 
|-
| [[Фибоначчиева куча]]
+
|[[Красно-черное дерево]]
| align="center" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| Куча, построенная на основе Фибоначчиева дерева. [[Фибоначчиево дерево]] (англ. ''Fibonacci tree'') {{---}} биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. ''red'') и "чёрный" (англ. ''black'').  При этом все листья дерева являются фиктивными и не содержат данных, но относятся к дереву и являются чёрными.
 
|-
 
|-
 +
| [[Декартово дерево]]
 +
| 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(n)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Бинарное дерево, в узлах которого хранится пары <tex> (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(\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(\log w)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</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)</tex> в большинстве других деревьев поиска, где <tex>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>
 +
| 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>\Theta(n)</tex>. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до <tex>\Theta(\log(n))</tex>
 +
|-
 +
|[[Fusion tree]]
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Дерево поиска, позволяющее хранить <tex>n</tex> <tex>w</tex>-битных чисел, используя <tex>O(n)</tex> памяти, и выполнять операции поиска за время <tex>O(\log_{w} n)</tex>. Эта структура данных была впервые предложена в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).
 +
|-
 +
| [[Сверхбыстрый цифровой бор|Цифровой бор]]
 +
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 +
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 +
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 +
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n \cdot w)</tex>
 +
| align="center" | [[Бор]], в котором в качестве строк используются двоичные записи чисел, включая ведущие нули. Таким образом он имеет глубину <tex>w</tex>.
 +
|-
 +
| [[Сверхбыстрый цифровой бор|Быстрый цифровой бор]]
 +
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 +
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 +
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n \cdot w)</tex>
 +
| align="center" | Улучшеная версия структуры цифрового бора.
 +
|-
 +
| [[Сверхбыстрый цифровой бор]]
 +
| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 +
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 +
| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 +
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Улучшеная версия структуры быстрого цифрового бора.
 +
|-
 +
!
 +
! colspan="9" align="center" | Статические структуры данных
 +
|-
 +
|[[Tango-дерево]]
 +
| colspan="2" align="center" style="background: #e5e5e5;" | -
 +
| colspan="2" align="center" style="background: #e5e5e5;" | -
 +
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | [[Дерево поиска, наивная реализация|Двоичное дерево поиска]], которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. Не поддерживает операции вставки и удаления, но перестраивается по ходу поисковых запросов, чтобы отвечать на них как можно оптимальней. Это лучшая известная реализация на данный момент.
 
|}
 
|}
==Применение==
+
 
* Алгоритм Дейкстры
+
==См. также==
* Алгоритм Прима
+
 
* Дискретно-событийное моделирование (англ. ''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]
+
* [[wikipedia:en:Search_data_structure|Wikidedia {{---}} Search data structure]]
* [http://en.wikipedia.org/wiki/Beap| Wikidedia {{---}} Beap]
+
* [http://habrahabr.ru/post/188010/ Habrahabr {{---}} Знай сложности алгоритмов ]
* [http://en.wikipedia.org/wiki/Binary_heap| Wikidedia {{---}} Binary heap]
 
* [http://en.wikipedia.org/wiki/Binomial_heap| Wikidedia {{---}} Binomial heap]
 
* [http://en.wikipedia.org/wiki/Brodal_queue| Wikidedia {{---}} Brodal queue]
 
* [http://en.wikipedia.org/wiki/D-ary_heap| Wikidedia {{---}} <tex>d</tex>-ary heap]
 
* [http://en.wikipedia.org/wiki/Fibonacci_heap| Wikidedia {{---}} Fibonacci heap]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
+
[[Категория: Деревья поиска]]
 
[[Категория: Структуры данных]]
 
[[Категория: Структуры данных]]

Текущая версия на 19:11, 4 сентября 2022

Поисковая структура данных — любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.

Простейшей, наиболее общей, но менее эффективной поисковой структурой является простая неупорядоченная последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур пропорциональна [math]n[/math], их построение окупится, даже если поступает лишь несколько запросов.

Тип

Статические поисковые структуры данных (англ. Offline search structures) предназначены для ответа на запросы на фиксированной базе данных.

Динамические поисковые структуры (англ. Online search structures) также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных. Любую динамическую структуру данных можно сделать статической, если запретить вставку и удаление. Также если множество ключей известно, то можно его заранее упорядочить так, чтобы избежать худших случаев в поисках в структурах данных.

Время работы

Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время — минимальное время работы алгоритма на каком-либо наборе. Худшее время — наибольшее время.

Используемая память

Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты составляют [math]O(n)[/math].

Сравнение структур данных

Сравним эффективность поисковых структур данных для реализации интерфейса упорядоченного множества. Время работы методов [math]Predecessor[/math] и [math]Successor[/math] совпадает с временем работы [math]Search[/math].

[math]n[/math] — количество хранимых чисел, каждое из которых представляется с помощью [math]w[/math] битов.

Insert Delete Search Память Описание
Среднее Худшее Среднее Худшее Среднее Худшее Среднее Худшее
Динамические структуры данных
Неотсортированный массив [math]O(1)[/math] [math]O(n)[/math] [math]O(1)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math] Наивная реализация, использующая динамический массив. Добавление происходит в конец массива, а для поиска элемента просто проходим по всему массиву.
Отсортированный массив [math]O(n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] То же самое, но теперь массив отсортирован. Поиск ускоряется за счёт возможности применить двоичный поиск. Вставка замедляется из-за необходимости поддерживать инвариант отсортированности.
Неотсортированный список [math]O(1)[/math] [math]O(1)[/math] [math]O(n)[/math] [math]O(n)[/math] Аналогично массиву, но храним данные в списке.
Отсортированный список [math]O(n)[/math] [math]O(1)[/math] [math]O(n)[/math] [math]O(n)[/math]
Дерево поиска, наивная реализация [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] Бинарное дерево поиска обладает следующим свойством: если [math]x[/math] — узел бинарного дерева с ключом [math]k[/math], то все узлы в левом поддереве должны иметь ключи, меньшие [math]k[/math], а в правом поддереве большие [math]k[/math].
Рандомизированное бинарное дерево поиска [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] Вариант двоичного дерево поиска с добавлением инвариата "случайности", что уменьнашает ожидаемую высоту дерева.
АВЛ-дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] Сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на [math]1[/math].
2-3 дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] Структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем B+ дерева.
B-дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] Cильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за [math]O(\log n)[/math]. B-дерево с [math]n[/math] узлами имеет высоту [math]O(\log n)[/math]. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время [math]O(\log n)[/math]
Красно-черное дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] Сбалансированное двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. red) и "чёрный" (англ. black). При этом все листья дерева являются фиктивными и не содержат данных, но относятся к дереву и являются чёрными.
Декартово дерево [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] Бинарное дерево, в узлах которого хранится пары [math] (x,y) [/math], где [math]x[/math] — это ключ, а [math]y[/math] — это приоритет. Также оно является двоичным деревом поиска по [math]x[/math] и пирамидой по [math]y[/math]. Предполагая, что все [math]x[/math] и все [math]y[/math] являются различными, получаем, что если некоторый элемент дерева содержит [math](x_0,y_0)[/math], то у всех элементов в левом поддереве [math]x \lt x_0[/math], у всех элементов в правом поддереве [math] x \gt x_0[/math], а также и в левом, и в правом поддереве имеем: [math] y \lt y_0[/math].
Splay-дерево [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] Двоичное дерево поиска. Оно позволяет находить быстрее те данные, которые использовались недавно, за счёт перемещения к корню (англ. Move to root). Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
Дерево ван Эмде Боаса [math]O(\log w)[/math] [math]O(\log w)[/math] [math]O(\log w)[/math] [math]O(2^w)[/math] Cтруктура данных, представляющая собой дерево поиска, позволяющее хранить целые неотрицательные числа в интервале [math][0;2^w)[/math] и осуществлять над ними все соответствующие дереву поиска операции. Проще говоря, данная структура позволяет хранить [math]w[/math]-битные числа.

Особенностью этой структуры является то, что все операции выполняются за [math]O(\log w)[/math], что асимптотически лучше, чем [math]O(\log n)[/math] в большинстве других деревьев поиска, где [math]n[/math] — количество элементов в дереве.

Список с пропусками [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] Вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.

Отсортированный связный список является простейшей структурой с временем поиска [math]\Theta(n)[/math]. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до [math]\Theta(\log(n))[/math]

Fusion tree [math]O(\log_{w} n)[/math] [math]O(\log_{w} n)[/math] [math]O(\log_{w} n)[/math] [math]O(n)[/math] Дерево поиска, позволяющее хранить [math]n[/math] [math]w[/math]-битных чисел, используя [math]O(n)[/math] памяти, и выполнять операции поиска за время [math]O(\log_{w} n)[/math]. Эта структура данных была впервые предложена в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).
Цифровой бор [math]O(w)[/math] [math]O(w)[/math] [math]O(w)[/math] [math]O(n \cdot w)[/math] Бор, в котором в качестве строк используются двоичные записи чисел, включая ведущие нули. Таким образом он имеет глубину [math]w[/math].
Быстрый цифровой бор [math]O(w)[/math] [math]O(w)[/math] [math]O(\log w)[/math] [math]O(n \cdot w)[/math] Улучшеная версия структуры цифрового бора.
Сверхбыстрый цифровой бор [math]O(\log w)[/math] [math]O(w)[/math] [math]O(\log w)[/math] [math]O(w)[/math] [math]O(\log w)[/math] [math]O(n)[/math] Улучшеная версия структуры быстрого цифрового бора.
Статические структуры данных
Tango-дерево - - [math]O(\log \log n)[/math] [math]O(n)[/math] Двоичное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. Не поддерживает операции вставки и удаления, но перестраивается по ходу поисковых запросов, чтобы отвечать на них как можно оптимальней. Это лучшая известная реализация на данный момент.

См. также

Источники информации