3622
правки
Изменения
Нет описания правки
Храним список левосторонних куч. Пока их количество больше <tex>1</tex>, из начала списка достаем две кучи, сливаем их и кладем в конец списка.
Покажем, почему это будет работать за <tex> O(n) </tex>.
Пусть на <tex> i </tex>-ом шаге алгоритма в нашем списке остались только кучи размера <tex> 2^i </tex>. На нулевом шаге у нас <tex> n </tex> куч из одного элемента, и на каждом следующем количество куч будет уменьшаться вдвое, а число вершин в куче будет увеличиваться вдвое. Слияние двух куч из <tex> n_i </tex> элементов выполняется за <tex> O(\log{n_i}) </tex>. Поэтому построение будет выполняться за
<tex dpi = 130>
\sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{n \cdot \log{n_i}}{2^i} =
n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{\log{2^i}}{2^i} =
n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{i}{2^i}
</tex>
Покажем, что сумма {{---}} <tex> O(1) </tex>, тогда и алгоритм будет выполняться за <tex> O(n) </tex>.
==Преимущества левосторонней кучи==
Нигде не делается уничтожающих присваиваний. Не создается новых узлов в <tex>merge</tex>. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реалзация <tex>merge</tex> является персистентной.
