Викиконспекты - Вклад участника [ru]

Сверхбыстрый цифровой бор

2013-06-11T11:56:48Z

217.66.159.60: /* Ссылки */

==Цифровой бор==
Работаем с целыми числами, которые представляются с помощью <tex>w</tex> битов, аналогично [[Дерево ван Эмде Боаса | дереву Ван Эмде Боаса]]. Мы можем их складывать, вычитать, умножать, сдвигать, производить с ними логические операции, адресоваться ими. В модели памяти <tex>unit~cost~RAM</tex>, которая сейчас применима к большинству процессоров, эти операции могут быть выполнены за <tex>O(1)</tex>.

Цифровой бор {{---}} [[Бор | бор]], в котором в качестве строк используются двоичные записи чисел, включая ведущие нули.
Таким образом он имеет глубину <tex>w</tex>.

Цифровой бор поддерживает операции <tex>insert, ~remove, ~find, ~succ, ~pred</tex>.

Добавление вершины происходит так же, как и в обычном боре.
Удаление можно выполнять лениво {{---}} просто убирая пометку с листа. А можно хранить число пометок в поддереве и удалять вершину, если это число стало равным нулю.

===succ===
Поиск следующего элемента осуществляется проходом от корня до вершины, из которой не можем пойти в нужную сторону. Если не смогли пойти влево <tex>(</tex>по ребру <tex>0)</tex>, то ответ {{---}} минимум в правом поддереве. Если не смогли пойти вправо, поднимаемся наверх, пока являемся правым ребенком; если стали левым, то поднимаемся, пока у вершины нет правого ребенка (если такой ситуации нет, то запрос больше всех элементов). Тогда ответ {{---}} минимум в правом поддереве.

Преимущества: простая реализация, занимает <tex>O(n \cdot w)</tex> памяти, все операции выполняются за <tex>O(w)</tex>.

Хуже дерева Ван Эмде Боаса по скорости, но памяти занимает меньше.

==Быстрый цифровой бор (x-fast-trie)==
[[File:Tsifrovoybor.jpg|thumb|500px|x-fast-trie]]
[[File:Min amp amp max.jpg|thumb|right|500px|Ссылки на минимум и максимум]]
Он по-прежнему будет занимать <tex>O(n \cdot w)</tex> памяти, но немодифицирующие операции <tex>(read{-}only)</tex> будут выполняться за <tex>O(\log w)</tex>.

Улучшим структуру: было два слабых места {{---}} подниматься вверх и искать минимум.

===succOrPred===
Первая модификация {{---}} занесем все элементы в двусвязный список в порядке, в котором они лежат в боре. Добавим операцию <tex>succOrPred</tex>, которая возвращает следующий или предыдущий в зависимости от того, что проще. Работает она так: спускается вниз до наибольшего общего префикса, а потом до минимума в правом дереве или же до максимума в левом. Тогда мы получим какой-то элемент списка и не более чем за два шага в списке сможем получить ответ на запрос.

Вторая модификация {{---}} добавим ссылки.
Операции поиска минимума и максимума дорогие, выполним их за <tex>O(1)</tex>. Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершину нет левого сына, отметим это одним битом, а вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации <tex>succOrPred</tex>. Если нет правого сына, то храним ссылку на максимум в левом поддереве.

===insert===
При вставке с помощью <tex>succOrPred</tex> и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины (у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.
<code style = "display: inline-block;">
// prefixes {{---}} HashMap всех префиксов бора
insert(x)
'''if''' prefixes.contains(x): // ''x'' содержится в боре
'''return'''
Node ''left'' = pred(x), ''right'' = succ(x), ''nodex'' = new Node(x)
insert ''nodex'' между ''left'' и ''right'' в двусвязном списке листьев
root = insertNode(root, w, ''nodex)
prefixes.addAll(allPrefixes(x))

insertNode(vertex, depth, x)
'''if''' ''vertex'' == <tex> \varnothing </tex>:
''vertex'' = new Node(left = <tex>\varnothing</tex>, right = <tex>\varnothing</tex>, terminal = depth == 0)
'''if''' ''depth'' == 0:
'''return''' ''vertex''
'''if''' depthBit(x) == 0: // depth-й бит, т. е. соответствующий текущей глубине
vertex.left = insertNode(vertex.left, depth - 1, x)
'''else''':
vertex.right = insertNode(vertex.right, depth - 1, x)
'''if''' vertex.left == <tex> \varnothing </tex>:
vertex.mark = ''HASNOLEFTSON''
vertex.left = ''x''
'''else if''' vertex.right == <tex> \varnothing </tex>:
vertex.mark = ''HASNORIGHTSON''
vertex.right = ''x''
</code>

===delete===
Удаление происходит аналогично добавлению. Модифицируем бор, чтобы в вершине был счётчик, сколько у неё вершин в поддереве. Если 0, то удаляем её совсем. Иначе же, если удалился какой-то из сыновей, то надо обновить ссылки min и max. Это сделать просто {{---}} ссылкой на минимум (максимум) в правом (левом) поддереве становится <tex> successor ~(predecessor)</tex> удалённой вершины.

Вставка и удаление выполняются за <tex>O(w)</tex>.

===binarySearch===
Пока что мы не добились асимптотического выигрыша {{---}} все операции по-прежнему выполняются за <tex>O(w)</tex>. Теперь слабое место {{---}} это поиск наибольшего общего префикса. Будем искать его двоичным поиском. Для этого занесём префиксы всех чисел в <tex> HashMap </tex> {{---}} [[Хеш-таблица |ассоциативный массив]], который по префиксу возвращает вершину в боре <tex>(</tex>чтобы избежать проблемы с ведущими нулями, используем при поиске маску вида <tex>0...01...1)</tex>. Запустим двоичный поиск по длине наибольшего общего префикса. Как только он вернет максимальный префикс, переходим в вершину (у этой вершины не может быть два сына, так как тогда поиск бы не завершился) и там за <tex>O(1)</tex> находим минимум или масимум, и за <tex>O(1)</tex> переходим по списку, если нужно.

Итого операции <tex>find, succ</tex> и <tex>pred</tex> будут выполняться за <tex>O(\log w)</tex>.

==Сверхбыстрый цифровой бор (y-fast-trie)==
[[File:Sverkhbystrybor.jpg|thumb|400px|y-fast-trie]]

Теперь усовершенствуем <tex>x{-}fast{-}trie</tex> до <tex>y{-}fast{-}trie</tex>, который занимает <tex>O(n)</tex> памяти, а все операции выполняются за <tex>O(\log w)</tex>, правда, для модифицирующих операций эта оценка будет амортизированной.

Уменьшим количество занимаемой памяти.
Пусть <tex>a_1 < a_2 < a_3 < ... < a_n</tex> {{---}} числа, которые нужно хранить в боре.
Выберем какое-то <tex>k</tex> (что за <tex>k</tex> {{---}} будет видно дальше). Разобьём их на <tex>s</tex> блоков размером от <tex dpi=150>\frac{k}{2}</tex> до <tex>2k</tex>, а точнее <tex>B_{11} < B_{12} < ... < B_{1n_{1}} < B_{21} < ... < B_{2n_{2}} < ... < B_{s1} < ... < B_{sn_{s}}</tex>

Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в <tex>x{-}fast{-}trie</tex>. Всего в <tex>x{-}fast{-}trie</tex> будет <tex dpi=150>O(\frac{2 \cdot n \cdot w} {k})</tex> элементов. Поэтому если выбрать <tex>k = \Omega(w)</tex>, то <tex>x{-}fast{-}trie</tex> будет занимать <tex>O(n)</tex> памяти.

Каждый лист <tex>x{-}fast{-}trie</tex> является представителем блока, а все остальные элементы блока (в т. ч. и представителя) подвесим к листу как сбалансированное двоичное дерево поиска. В дереве может храниться от <tex dpi=150>\frac{w}{2}</tex> до <tex>2w</tex> элементов, поэтому его высота {{---}} <tex>O(\log w)</tex>.

Все деревья поиска занимают <tex>O(n)</tex> памяти, и <tex>x{-}fast{-}trie</tex> {{---}} <tex>O(n)</tex> памяти. Поэтому <tex>y{-}fast{-}trie</tex> тоже занимает <tex>O(n)</tex> памяти.

===find===
Находим <tex>succ(x)</tex> среди представителей в <tex>x{-}fast{-}trie</tex>, а потом запускаем поиск <tex>succ(x)</tex> в дереве, подвешенном к листу <tex>x</tex>, а также в дереве, подвешенном к листу <tex>pred(x)</tex> среди представителей в <tex>x{-}fast{-}trie</tex>. Представителем дерева является необязательно минимальный или максимальный элемент, поэтому нужно запустить в двух деревьях. Заметим, что мы ищем элемент только в двух деревьях, так как искомый элемент точно находится между своими следующим и предыдущим элементами.
<tex>O(\log w)</tex> на поиск в <tex>x{-}fast{-}trie</tex> и <tex>O(\log w)</tex> на поиск в деревьях поиска, поэтому итогая асимптотика {{---}} <tex>O(\log w)</tex>.

<tex>succ</tex> и <tex>pred</tex> выполняются аналогично.

===insert===
Вставка элемента <tex>x</tex> происходит следующим образом: найдём <tex>succ(x)</tex> и вставим его в подвешенное к листу дерево. Но может возникнуть плохая ситуация: размер дерева станет <tex>2 \cdot w + 1</tex>. Тогда поступим следующим образом: удалим наше дерево из <tex>x{-}fast{-}trie</tex>, разделим его на элементы, из которых построим два дерева размером <tex>w</tex> и <tex>w + 1</tex>, и вставим в <tex>x{-}fast{-}trie</tex> их оба.

===delete===
Удаление происходит аналогично, только если размер дерева станет <tex dpi=150>\frac{w}{2} - 1</tex>, то надо его слить с любым соседним деревом. А если после слияния размер получившегося дерева станет больше <tex>2 \cdot w</tex>, то надо его разделить аналогично предыдущему случаю.

[[АВЛ-дерево |АВЛ-деревья]] или [[Красно-черное дерево |красно-чёрные]] позволяют выполнять слияние и разделение за линейное время, поэтому операции вставки и удаления выполняются за <tex>O(w)</tex>.

===Асимптотика===
Заметим, что вставка, которая не модифицирует верхний бор, выполняется за истинный <tex>\log w</tex>, также и <tex>succ, pred</tex>.
Плохие операции {{---}} которые модифицируют верхний бор. Но они не происходят слишком часто.

Применим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слияние массивов осуществляется за <tex>O(w)</tex>, как и разделение. Поэтому если мы накопим <tex>\Omega(w)</tex> дополнительных денег на дешёвых операциях, то сумеем расплатиться за все остальные, просто положив константное число дополнительных монет во время каждой операции. Худший для разделения случай произойдет, если мы дальше будем только добавлять элементы {{---}} было <tex dpi=150>\frac{w}{2} - 1</tex> и <tex>2 \cdot w</tex>, слили, стало больше <tex>2 \cdot w</tex>, разделили, таким образом получили два дерева с <tex dpi=150>\frac{5\cdot w}{4}</tex> элементами. Худший случай для слияния, когда у нас <tex>w</tex> элементов (просиходит после разделения <tex>2 \cdot w + 1</tex> дерева). Заметим, что в каждом случае дерево находится на расстоянии <tex>\Theta(w)</tex> от границ. Следовательно, если мы будем класть определённое константное число монет, то скопим их достаточно, чтобы расплатиться за дорогие операции слияния и разделения деревьев.

Получаем амортизированную оценку <tex>O(\log w)</tex> и истинную {{---}} <tex>O(w)</tex>.

Получилась та же оценка на операции, что и у дерева Ван Эмде Боаса, но структура данных занимает <tex>O(n)</tex> памяти.

==Ссылки==
*[[wikipedia:Y-fast_trie | Y-fast trie {{---}} Wikipedia]]
*[[wikipedia:X-fast_trie | X-fast trie {{---}} Wikipedia]]
*[http://compscicenter.ru/program/lecture/6902 Лекция А. С. Станкевича в Computer Science Center]

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

Левосторонняя куча

2013-06-11T11:53:20Z

217.66.159.60: /* Ссылки */

[[Файл:LeftistHeap.jpg|400px|thumb|right|Левосторонняя куча]]
==Определение==
Левосторонние деревья были изобретены Кларком Крейном (Clark Allan Crane), свое название они получили из-за того, что левое поддерево обычно длиннее правого.
{{Определение
|definition='''Левосторонняя куча (leftist heap)''' {{---}} двоичное левосторонее [[Дерево, эквивалентные определения|дерево]] (не обязательно сбалансированное), но с соблюдением [[Двоичная куча#Определение|порядка кучи]] (heap order).}}
{{Лемма
|id=lemma1
|about=1
|statement=В двоичном дереве с <tex>n</tex> вершинами существует свободная позиция на глубине не более <tex>\log{n}</tex>.
|proof=Если бы все свободные позиции были на глубине более логарифма, то мы получили бы полное дерево с количеством вершин более <tex>n</tex>. }}

Левосторонняя куча накладывает на двоичное дерево дополнительное условие.
Ближайшая свободная позиция должна быть самой правой позицией в дереве. То есть помимо обычного условия кучи выполняется следующее:

{{Определение
|definition=Условие левосторонней кучи. Пусть <tex>dist(u)</tex> {{---}} расстояние от вершины <tex>u</tex> до ближайшей свободной позиции в ее поддереве. У пустых позиций <tex>dist = 0</tex>. Тогда потребуем для любой вершины <tex>u : dist(u.L)\ge dict(u.R)</tex>.}}

Если для какой- то вершины это свойство не выполняется, то это легко устраняется: можно за <tex>O(1)</tex> поменять местами левого и правого ребенка, что не повлияет на порядок кучи.

==Поддерживаемые операции==
===merge===
Слияние двух куч.

'''merge'''(x, y) // x, y {{---}} корни двух деревьев
'''if''' x == <tex> \varnothing </tex>: '''return''' y
'''if''' y == <tex> \varnothing </tex>: '''return''' x
'''if''' y.key < x.key:
x <tex>\leftrightarrow</tex> y
// Воспользуемся тем, что куча левосторонняя. Правая ветка {{---}} самая короткая и не длиннее логарифма.
// Пойдем направо и сольем правое поддерево с у.
x.R = '''merge'''(x.R, y)
// Могло возникнуть нарушение левостороннести кучи.
'''if''' dist(x.R) > dist(x.L):
x.L <tex>\leftrightarrow</tex> x.R
dist(x) = min(dist(x.L), dist(x.R)) + 1 // пересчитаем расстояние до ближайшей свободной позиции
'''return''' x
// Каждый раз идем из уже существующей вершины только в правое поддерево {{---}} не более логарифма вызовов (по лемме)

Левосторонняя куча относится к сливаемым кучам: остальные операции легко реализуются с помощью операции слияния.

===insert===
Вставка новой вершины в дерево. Новое левостороннее дерево, состоящее из одной вершины, сливается с исходным.
===extractMin===
Как и у любой другой двоичной кучи, минимум хранится в корне. Извлекаем минимальное значение, удаляем корень, сливаем левое и правое поддерево корня. Возвращает пару из извлеченной вершины и новой кучи.
===delete===
Аналогично удаляется любой элемент {{---}} на его место ставится результат слияния его детей. Но так просто любой элемент удалить нельзя {{---}} на пути от этого элемента к корню может нарушиться левостороннесть кучи. А до корня мы дойти не можем, так как элемент может находиться на линейной глубине. Поэтому удаление реализуется с помощью <tex>decrease key</tex>. Уменьшаем ключ до <tex>-\infty</tex>, затем извлекаем минимальное значение.
===decreaseKey===
{{Лемма
|id=lemma2
|about=2
|statement=У левостороннего дерева с правой ветвью длинны <tex>h</tex> количество узлов <tex>n \ge 2^{h} - 1</tex>.
|proof=Индукция по h.

При <tex>h = 1</tex> {{---}} верно.

При <tex>h > 1</tex> левое и правое поддеревья исходного дерева левосторонние, а <tex>dist</tex> от их корней больше либо равен <tex>h - 1</tex>.

По индукции число узлов в каждом из них больше или равно <tex>2^{h - 1} - 1</tex>, тогда во все дереве <tex>n \ge (2^{h - 1} - 1) + (2^{h - 1} - 1) + 1 = 2^{h} - 1</tex> узлов.}}
====Алгоритм====
* Найдем узел <tex>x</tex>, вырежем поддерево с корнем в этом узле.
* Пройдем от предка вырезанной вершины, при этом пересчитывая <tex>dist</tex>. Если <tex>dist</tex> левого сына вершины меньше <tex>dist</tex> правого, то меняем местами поддеревья.
* Уменьшаем ключ данного узла и сливаем два дерева: исходное и вырезанное.
{{Лемма
|id=lemma3
|about=3
|statement= Нужно транспонировать не более <tex>\log{n}</tex> поддеревьев.
|proof=Длина пути от вершины до корня может быть и <tex>O(n)</tex>, но нам не нужно подниматься до корня {{---}} достаточно подняться до вершины, у которой свойство левосторонней кучи уже выполнено. Транспонируем только если <tex>dist(x.L) < dist(x.R)</tex>, но <tex>dist(x.R) \le \log{n}</tex>. На каждом шаге, если нужно транспонируем и увеличиваем <tex>dist++</tex>, тогда <tex>dist</tex> увеличится до <tex>\log{n}</tex> и обменов уже не надо будет делать.}}
Таким образом, мы восстановили левостороннесть кучи за <tex>O(\log{n})</tex>. Поэтому асимптотика операции <tex> decreaseKey </tex> {{---}} <tex>O(\log{n})</tex>.

==Построение кучи за O(n)==
Храним список левосторонних куч. Пока их количество больше <tex>1</tex>, из начала списка достаем две кучи, сливаем их и кладем в конец списка.

Покажем, почему это будет работать за <tex> O(n) </tex>.

Пусть на <tex> i </tex>-ом шаге алгоритма в нашем списке остались только кучи размера <tex> 2^i </tex>. На нулевом шаге у нас <tex> n </tex> куч из одного элемента, и на каждом следующем количество куч будет уменьшаться вдвое, а число вершин в куче будет увеличиваться вдвое. Слияние двух куч из <tex> n_i </tex> элементов выполняется за <tex> O(\log{n_i}) </tex>. Поэтому построение будет выполняться за

<tex dpi = 130>
\sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{n \cdot \log{n_i}}{2^i} =
n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{\log{2^i}}{2^i} =
n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{i}{2^i}
</tex>

Покажем, что сумма {{---}} <tex> O(1) </tex>, тогда и алгоритм будет выполняться за <tex> O(n) </tex>. Найдём сумму [[Определение суммы числового ряда|ряда]], заменив его на эквивалентный [[Определение функционального ряда|функциональный]]:

<tex dpi = 130>
\sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{i}{2^i} < \sum\limits_{i = 1}^{\infty } \genfrac{}{}{}{0}{i}{2^i} \\
f(x) = \sum\limits_{i = 1}^{\infty } \Bigl. i \cdot x^i \Bigr|_{x = \frac{1}{2}},
~\genfrac{}{}{}{0}{f(x)}{x} = \sum\limits_{i = 1}^{\infty } i \cdot x^{i - 1},
~\int\genfrac{}{}{}{0}{f(x)}{x} = \sum\limits_{i = 1}^{\infty } x^i =~\genfrac{}{}{}{0}{1}{1 - x} - 1, \\
~\genfrac{}{}{}{0}{f(x)}{x} = (\genfrac{}{}{}{0}{1}{1 - x} - 1)' = \genfrac{}{}{}{0}{1}{(1 - x)^2},
~f(x) = \genfrac{}{}{}{0}{x}{(1 - x)^2}
</tex>

После подстановки <tex> x = \genfrac{}{}{}{0}{1}{2} </tex> получаем, что сумма равна <tex> 2 </tex>. Следовательно, построение кучи таким образом произойдёт за <tex> O(n) </tex>.
==Преимущества левосторонней кучи==
Нигде не делается уничтожающих присваиваний. Не создается новых узлов в <tex>merge</tex>. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реализация <tex>merge</tex> является персистентной.

==Ссылки==
1. [http://compscicenter.ru/program/lecture/6829 Лекция "Приоритетные очереди" А. С. Станкевича в Computer Science Center]

2. [http://www.intuit.ru/studies/courses/100/100/lecture/1539?page=1 Левосторонние кучи. Интуит.]

3. [[wikipedia:Leftist_tree|Wikipedia {{---}} Leftist tree]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]