668
правок
Изменения
→Построение кучи за O(N)
|proof=
Подсчитаем суммарное число операций за все время работы алгоритма. Пусть <tex> H </tex> высота дерева. Подсчитаю сумму, сколько нужно операций для перемещения вершин в лист. <tex dpi = "160"> \frac{N}{4} </tex> вершин опустятся на 1, <tex dpi ="160"> \frac{N}{8} </tex> опустятся на 2 итд. Получим сумму
<tex dpi = "160"> \frac{N}{2} \cdot {\sum_{i = 1}^H \limits}\frac{i}{2^i}.</tex>
<tex dpi = "160"> {\sum_{i = 1}^H \limits}\frac{i}{2^i} = 4 </tex> Откуда получаем оценку <tex> O(N) </tex>.
== Источники ==
