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

2015-03-30T18:43:15Z

217.66.156.147: /* Условие кучи */

[[Файл: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.left)\geqslant dist(u.right)</tex>.}}

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

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

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

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

===insert===
Вставка новой вершины в дерево. Новое левостороннее дерево, состоящее из одной вершины, сливается с исходным.
===extractMin===
Как и у любой другой двоичной кучи, минимум хранится в корне. Извлекаем минимальное значение, удаляем корень, сливаем левое и правое поддерево корня. Возвращает пару из извлеченной вершины и новой кучи.
===delete===
Аналогично удаляется любой элемент {{---}} на его место ставится результат слияния его детей. Но так просто любой элемент удалить нельзя {{---}} на пути от этого элемента к корню может нарушиться левостороннесть кучи. А до корня мы дойти не можем, так как элемент может находиться на линейной глубине. Поэтому удаление реализуется с помощью <tex>\mathrm{decreaseKey}</tex>. Уменьшаем ключ до <tex>-\infty</tex>, затем извлекаем минимальное значение.
===decreaseKey===
{{Лемма
|id=lemma2
|about=2
|statement=У левостороннего дерева с правой ветвью длинны <tex>h</tex> количество узлов <tex>n \geqslant 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 \geqslant (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.left) < dist(x.right)</tex>, но <tex>dist(x.right) \leqslant \log{n}</tex>. На каждом шаге, если нужно транспонируем и увеличиваем <tex>dist</tex>, тогда <tex>dist</tex> увеличится до <tex>\log{n}</tex> и обменов уже не надо будет делать.}}
Таким образом, мы восстановили левостороннесть кучи за <tex>O(\log{n})</tex>. Поэтому асимптотика операции <tex>\mathrm{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} = \sum\limits_{i = 1}^{\infty } (x^i)' = (\sum\limits_{i = 1}^{\infty } x^i)' \\
~\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>\mathrm{merge}</tex>. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реализация <tex>\mathrm{merge}</tex> является персистентной.

==Источники информации==
* [http://compscicenter.ru/program/lecture/6829 Лекция "Приоритетные очереди" А. С. Станкевича в Computer Science Center]
* [http://www.intuit.ru/studies/courses/100/100/lecture/1539?page=1 Левосторонние кучи. Интуит.]
* [[wikipedia:Leftist_tree|Wikipedia {{---}} Leftist tree]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]

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

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