Изменения
Нет описания правки
|id=lemma1
|about=1
|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.L)>= \ge dict(xu.R)</tex>.}}
Если для какой- то вершины это свойство не выполняется, то это легко устраняется: можно за О<tex>O(1) </tex> поменять местами левого и правого ребенка, что не повлияет на порядок кучи.
==Поддерживаемые операции==
===merge===
Слияние двух куч. <code>merge(x,y) //x,y – корни двух деревьев
if x == NULL return y
if y == NULL return x
update dist(x) //dist(x) = min(dist(x.L), dist(x.R)) + 1
return x;
//Каждый раз идет в уже существующей вершине только в правое поддерево — не более логарифма вызовов (по лемме).</code>
Левосторонняя куча относится к сливаемым кучам: остальные операции легко реализуются с помощью операции слияния.
Как и у любой другой двоичной кучи, минимум хранится в корне. Извлекаем минимальное значение, удаляем корень, сливаем левое и правое поддерево корня. Возвращает пару из извлеченной вершины и новой кучи.
===delete===
Аналогично удаляется любой элемент — на его место ставится результат слияния его детей. Но так просто любой элемент удалить нельзя — на пути от этого элемента к корню может нарушиться левостороннесть кучи. А до корня мы дойти не можем, так как элемент может находиться на линейной глубине. Поэтому удаление реализуется с помощью <tex>decrease key</tex>. Уменьшаем ключ до <tex>-inf\infty</tex>, затем извлекаем минимальное значение.
===decKey===
{{Лемма
|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> узлов.}}
====Алгоритм====
1. Найдем узел х<tex>x</tex>, вырежем поддерево с корнем в этом узле.
2. Пройдем от предка вырезанной вершины, при этом пересчитывая <tex>dist</tex>. Если <tex>dist </tex> левого сына вершины меньше <tex>dist </tex> правого, то меняем местами поддеревья.
{{Лемма
|id=lemma3
|about=3
|statement= Нужно транспонировать не более logn <tex>\log{n}</tex> поддеревьев. |proof=Длина пути от вершины до корня может быть и <tex>O(n)</tex>, но нам не нужно подниматься до корня — достаточно подняться до вершины, у которой свойство левостороннести уже выполнено. Транспонируем только если <tex>dist(x.L) < dist(x.R)</tex>, но <tex>dist(x.R) \le \log{n}<= logn/tex>. На каждом шаге, если нужно транспонируем и увеличиваем <tex>dist++</tex>, тогда <tex>dist </tex> увеличится до logn <tex>\log{n}</tex> и обменов уже не надо будет делать.}}Таким образом, мы восстановили левостороннесть кучи за <tex>O(logn\log{n})</tex>.
3. Уменьшаем ключ данного узла и сливаем два дерева: исходное и вырезанное. <tex>O(logn\log{n})</tex>==Построение кучи за О<tex>O(n)</tex>==Храним список левосторонних куч. Пока их количество больше <tex>1</tex>, из начала списка достаем две кучи, сливаем их и кладем в конец списка.
==Преимущества левосторонней кучи==
Нигде не делается уничтожающих присваиваний. Не создается новых узлов в <tex>merge</tex>. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реалзация merge является персистентной.
