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