Изменения

[[Файл:LeftistHeap.jpg|400px|thumb|right|Левосторонняя куча]]==ОпределениеУсловие кучи==

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

|statement=В двоичном дереве с <tex>n </tex> вершинами существует свободная позиция на глубине не более logn<tex>\log{n}</tex>.|proof=Если бы все свободные позиции были на глубине более логарифма, то мы получили бы полное дерево с количеством вершин более <tex>n</tex>. }}

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

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

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

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

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

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

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

 При <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> узлов.}}

1. * Найдем узел х<tex>x</tex>, вырежем поддерево с корнем в этом узле.2. * Пройдем от предка вырезанной вершины, при этом пересчитывая <tex>dist</tex>. Если <tex>dist </tex> левого сына вершины меньше <tex>dist </tex> правого, то меняем местами поддеревья.* Уменьшаем ключ данного узла и сливаем два дерева: исходное и вырезанное.

|statement= Нужно транспонировать не более logn <tex>\log{n}</tex> поддеревьев. |proof=Длина пути от вершины до корня может быть и <tex>O(n)</tex>, но нам не нужно подниматься до корня — {{---}} достаточно подняться до вершины, у которой свойство левостороннести левосторонней кучи уже выполнено. Транспонируем только если <tex>dist(x.Lleft) < dist(x.Rright)</tex>, но <tex>dist(x.Rright) \leqslant \log{n}<= logn/tex>. На каждом шаге, если нужно транспонируем и увеличиваем <tex>dist++</tex>, тогда <tex>dist </tex> увеличится до logn <tex>\log{n}</tex> и обменов уже не надо будет делать.}}Таким образом, мы восстановили левостороннесть кучи за <tex>O(logn\log{n})3. Уменьшаем ключ данного узла и сливаем два дерева: исходное и вырезанное</tex>. Поэтому асимптотика операции <tex>\mathrm{decreaseKey} </tex> {{---}} <tex>O(logn\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 > \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \dfrac{n \cdot \log{n_i}}{2^i} = n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \dfrac{\log{2^i}}{2^i} = n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \dfrac{i}{2^i}</tex> Покажем, что сумма {{---}} <tex> O(1) </tex>, тогда и алгоритм будет выполняться за <tex> O(n) </tex>. Найдём сумму [[Определение суммы числового ряда|ряда]], заменив его на эквивалентный [[Определение функционального ряда|функциональный]]: <tex> \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \dfrac{i}{2^i} < \sum\limits_{i = 1}^{\infty } \dfrac{i}{2^i} \\f(x) = \sum\limits_{i = 1}^{\infty } \Bigl. i \cdot x^i \Bigr|_{x = \frac{1}{2}} \\ ~\dfrac{f(x)}{x} = \sum\limits_{i = 1}^{\infty } i \cdot x^{i - 1} = \sum\limits_{i = 1}^{\infty } (x^i)' = \left(\sum\limits_{i = 1}^{\infty } x^i \right)' \\~\int\dfrac{f(x)}{x} = \sum\limits_{i = 1}^{\infty } x^i =~\dfrac{1}{1 - x} - 1 \\~\dfrac{f(x)}{x} = \left(\dfrac{1}{1 - x} - 1\right)' = \dfrac{1}{(1 - x)^2} \\~f(x) = \dfrac{x}{(1 - x)^2}</tex> После подстановки <tex> x = \dfrac{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]] [[Категория: Дискретная математика и алгоритмы]][[Категория: Приоритетные очереди]][[Категория: Структуры данных]]