Изменения
Нет описания правки
|statement=У левостороннего дерева с правой ветвью длинны h количество узлов n>= 2^h – 1.
|proof=Индукция по h.
При h = 1 – верно.
При h > 1 левое и правое поддеревья исходного дерева левосторонние, а dist от их корней >= h – 1. По индукции число узлов в каждом из них >=2^(h - 1) – 1, тогда во все дереве n >= (2^(h – 1) – 1) + (2^(h – 1) – 1) +1 = 2^h – 1 узлов.}}
====Алгоритм====
1. Найдем узел х, вырежем поддерево с корнем в этом узле.
2. Пройдем от предка вырезанной вершины, при этом пересчитывая dist. Если dist левого сына вершины меньше dist правого, то меняем местами поддеревья.
{{Лемма
|id=lemma3
|proof=Длина пути от вершины до корня может быть и O(n), но нам не нужно подниматься до корня — достаточно подняться до вершины, у которой свойство левостороннести уже выполнено. Транспонируем только если dist(x.L) < dist(x.R), но dist(x.R) <= logn. На каждом шаге, если нужно транспонируем и увеличиваем dist++, тогда dist увеличится до logn и обменов уже не надо будет делать.}}
Таким образом, мы восстановили левостороннесть кучи за O(logn)
3. Уменьшаем ключ данного узла и сливаем два дерева: исходное и вырезанное. O(logn)
==Построение кучи за О(n)==
