3622
правки
Изменения
мелкий рефакторинг
{{Определение
|definition='''Условие левосторонней кучи'''. Пусть <tex>dist(u)</tex> {{---}} расстояние от вершины <tex>u</tex> до ближайшей свободной позиции в ее поддереве. У пустых позиций <tex>dist = 0</tex>. Тогда потребуем для любой вершины <tex>u : dist(u.L)\ge geqslant dict(u.R)</tex>.}}
Если для какой- то вершины это свойство не выполняется, то это легко устраняется: можно за <tex>O(1)</tex> поменять местами левого и правого ребенка, что не повлияет на порядок кучи.
Слияние двух куч.
'''mergefunction'''merge(x, y): // x, y {{---}} корни двух деревьев
'''if''' x == <tex> \varnothing </tex>: '''return''' y
'''if''' y == <tex> \varnothing </tex>: '''return''' x
|id=lemma2
|about=2
|statement=У левостороннего дерева с правой ветвью длинны <tex>h</tex> количество узлов <tex>n \ge geqslant 2^{h} - 1</tex>.
|proof=Индукция по h.
При <tex>h > 1</tex> левое и правое поддеревья исходного дерева левосторонние, а <tex>dist</tex> от их корней больше либо равен <tex>h - 1</tex>.
По индукции число узлов в каждом из них больше или равно <tex>2^{h - 1} - 1</tex>, тогда во все дереве <tex>n \ge geqslant (2^{h - 1} - 1) + (2^{h - 1} - 1) + 1 = 2^{h} - 1</tex> узлов.}}
====Алгоритм====
* Найдем узел <tex>x</tex>, вырежем поддерево с корнем в этом узле.
|about=3
|statement= Нужно транспонировать не более <tex>\log{n}</tex> поддеревьев.
|proof=Длина пути от вершины до корня может быть и <tex>O(n)</tex>, но нам не нужно подниматься до корня {{---}} достаточно подняться до вершины, у которой свойство левосторонней кучи уже выполнено. Транспонируем только если <tex>dist(x.L) < dist(x.R)</tex>, но <tex>dist(x.R) \le 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>.
<tex dpi = 130>
\sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{i}{2^i} < \sum\limits_{i = 1}^{\infty } \genfrac{}{}{}{0}{i}{2^i} \\
f(x) = \sum\limits_{i = 1}^{\infty } \Bigl. i \cdot x^i \Bigr|_{x = \frac{1}{2}}, \\ ~\genfrac{}{}{}{0}{f(x)}{x} = \sum\limits_{i = 1}^{\infty } i \cdot x^{i - 1},= \sum\limits_{i = 1}^{\infty } (x^i)' = (\sum\limits_{i = 1}^{\infty } x^i)' \\~\int\genfrac{}{}{}{0}{f(x)}{x} = \sum\limits_{i = 1}^{\infty } x^i =~\genfrac{}{}{}{0}{1}{1 - x} - 1, \\~\genfrac{}{}{}{0}{f(x)}{x} = (\genfrac{}{}{}{0}{1}{1 - x} - 1)' = \genfrac{}{}{}{0}{1}{(1 - x)^2},\\
~f(x) = \genfrac{}{}{}{0}{x}{(1 - x)^2}
</tex>
