3622
правки
Изменения
Нет описания правки
</tex>
Покажем, что сумма {{---}} <tex> O(1) </tex>, тогда и алгоритм будет выполняться за <tex> O(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},~\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> После подстановки <tex> x = \genfrac{}{}{}{0}{1}{2} </tex> получаем, что сумма равна <tex> 2 </tex>. Следовательно, построение кучи таким образом произойдёт за <tex> O(n) </tex>.
==Преимущества левосторонней кучи==
Нигде не делается уничтожающих присваиваний. Не создается новых узлов в <tex>merge</tex>. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реалзация <tex>merge</tex> является персистентной.
