Изменения

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

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

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

<code> '''merge'''(x,y) //x,y – {{---}} корни двух деревьев '''if''' x == NULL <tex> \varnothing </tex>: '''return''' y '''if''' y == NULL <tex> \varnothing </tex>: '''return''' x '''if''' y.key < x.key :

//Воспользуемся тем, что куча левосторонняя. Правая ветка — {{---}} самая короткая и не длиннее логарифма. //Пойдем направо и сольем правое поддерево с у. x.R <tex>\leftarrow</tex> = '''merge'''(x.R, y) //Могло возникнуть нарушение левостороннести кучи.

'''update''' dist(x) //dist(x) = min(dist(x.L), dist(x.R)) + 1// пересчитаем расстояние до ближайшей свободной позиции '''return''' x; //Каждый раз идет в идем из уже существующей вершине вершины только в правое поддерево — {{---}} не более логарифма вызовов (по лемме).</code>

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

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

1. * Найдем узел <tex>x</tex>, вырежем поддерево с корнем в этом узле. 2. * Пройдем от предка вырезанной вершины, при этом пересчитывая <tex>dist</tex>. Если <tex>dist</tex> левого сына вершины меньше <tex>dist</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>.