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