Изменения

{{Определение | definition ='''<tex>d - </tex> куча''' {{---}} это куча в которой не 2 потомка, а <tex> d </tex> потомков. }}Дан массив <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]</tex> и <tex>...A[2i+2d]</tex>). Делаем sift_down для вершин имеющих хотя бы одного потомка (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены). На выходе получим искомую кучу.

Число вершин на высоте <tex>h</tex> в куче из <tex>n</tex> элементов не превосходит <tex dpi = "160"> \left \lceil \frac{n}{2d^h} \right \rceil </tex>. Высота кучи не превосходит <tex> \log_{2d} n </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит <tex dpi = "160"> \sum_{h = 1}^H \limits\frac{n}{2d^h}\ cdot d</tex> <tex dpi = "150"> \cdot h </tex> <tex dpi = "160">= n \cdot d \cdot {\sum_{h = 1}^H \limits}\frac{h}{2d^h}. </tex> <tex dpi = "160"> {\sum_{h = 1}^\infty \limits}\frac{h}{d^h}= 2. </tex>

Все операции, которые делались c бинарной кучей, допустимы и для <tex>d</tex> - кучи. Посчитаем время построения <tex> d</tex> - кучи. В этом случае время работы не превзойдет <tex dpi = "140">N \cdot d </tex> <tex dpi = "160" > \cdot {\sum_{i = 1}^H \limits}\frac{i}{d^i} .</tex>