3622
правки
Изменения
→decreaseKey
При <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> узлов.}}
====Алгоритм====
* Найдем узел <tex>x</tex>, вырежем поддерево с корнем в этом узле.
|proof=Длина пути от вершины до корня может быть и <tex>O(n)</tex>, но нам не нужно подниматься до корня {{---}} достаточно подняться до вершины, у которой свойство левосторонней кучи уже выполнено. Транспонируем только если <tex>dist(x.L) < dist(x.R)</tex>, но <tex>dist(x.R) \leqslant \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>.
==Построение кучи за O(n)==
