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