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