Изменения

==ОпределениеУсловие кучи==

|definition='''Левосторонняя куча ''' (англ. ''leftist heap)''' ) {{---}} двоичное левосторонее [[Дерево, эквивалентные определения|дерево]] (не обязательно сбалансированное), но с соблюдением [[Двоичная куча#Определение|порядка кучи]] (heap order).}}'''Свободной позицией''' назовем место в дереве, куда может быть вставлена новая вершина. Само дерево будет являться свободной позицией, если оно не содержит вершин. Если же у какой-то внутренней вершины нет сына, то на его месте {{---}} ''свободная позиция''.

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

'''mergeLeftistHeap'''merge(x, y) : <font color=darkgreen>// x, y {{---}} корни двух деревьев</font> '''if''' x == <tex> \varnothing </tex>: '''return''' y '''if''' y == <tex> \varnothing </tex>: '''return''' x

swap(x <tex>\leftrightarrow</tex> , y) <font color=darkgreen>// Воспользуемся тем, что куча левосторонняя. Правая ветка {{---}} самая короткая и не длиннее логарифма. // Пойдем направо и сольем правое поддерево с у.</font> x.R right = '''merge'''(x.Rright, y) <font color=darkgreen>// Могло возникнуть нарушение левостороннести кучи.</font> '''if''' dist(x.Rright) > dist(x.Lleft): swap(x.L <tex>\leftrightarrow</tex> left, x.Rright) dist(x) = min(dist(x.Lleft), dist(x.Rright)) + 1 <font color=darkgreen>// пересчитаем расстояние до ближайшей свободной позиции</font>

<font color=darkgreen>// Каждый раз идем из уже существующей вершины только в правое поддерево {{---}} не более логарифма вызовов (по лемме)</font>

Аналогично удаляется любой элемент {{---}} на его место ставится результат слияния его детей. Но так просто любой элемент удалить нельзя {{---}} на пути от этого элемента к корню может нарушиться левостороннесть кучи. А до корня мы дойти не можем, так как элемент может находиться на линейной глубине. Поэтому удаление реализуется с помощью <tex>decrease key\mathrm{decreaseKey}</tex>. Уменьшаем ключ до <tex>-\infty</tex>, затем извлекаем минимальное значение.

|statement=У левостороннего дерева с правой ветвью длинны длины <tex>h</tex> количество узлов <tex>n \ge geqslant 2^{h} - 1</tex>.

По индукции число узлов в каждом из них больше или равно <tex>2^{h - 1} - 1</tex>, тогда во все всем дереве <tex>n \ge geqslant (2^{h - 1} - 1) + (2^{h - 1} - 1) + 1 = 2^{h} - 1</tex> узлов.}}

|proof=Длина пути от вершины до корня может быть и <tex>O(n)</tex>, но нам не нужно подниматься до корня {{---}} достаточно подняться до вершины, у которой свойство левосторонней кучи уже выполнено. Транспонируем только если <tex>dist(x.Lleft) < dist(x.Rright)</tex>, но <tex>dist(x.Rright) \le 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>. 

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

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

После подстановки <tex> x = \genfrac{}{}{}{0}dfrac{1}{2} </tex> получаем, что сумма равна <tex> 2 </tex>. Следовательно, построение кучи таким образом произойдёт за <tex> O(n) </tex>. 

Нигде не делается уничтожающих присваиваний. Не создается новых узлов в <tex>\mathrm{merge}</tex>. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реализация <tex>\mathrm{merge}</tex> является персистентной. ==Ссылки==1. [http://compscicenter.ru/program/lecture/6829 Лекция "Приоритетные очереди" А. С. Станкевича в Computer Science Center]

2==Источники информации==* [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]]