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