Изменения

'''<tex>d - D</tex> -куча''' {{---}} это куча , в которой не 2 потомкау каждого элемента, кроме, возможно, элементов на последнем уровне, а ровно <tex> d D</tex> потомков.

 Дан массив <tex> A[0.. n N - 1]. </tex> Требуется построить <tex> d - 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+dD]</tex>). Делаем Сделаем sift_down для вершин , имеющих хотя бы одного потомка , (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены). На выходе получим искомую кучу.  

|proof=Число вершин на высоте <tex>h</tex> в куче из <tex>nN</tex> элементов не превосходит <tex dpi = "160120"> \left \lceil \frac{nN}{dD^h} \right \rceil </tex>. Высота кучи не превосходит <tex> \log_{dD} n N </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит <tex dpi = "160"> \sum_{h = 1}^H \limits\frac{N}{D^h} \cdot D </tex> <tex dpi = "150"> \cdot h </tex> <tex dpi = "160"> = N \cdot D \cdot {\sum_{h = 1}^H \limits}\frac{h}{D^h}. </tex> Докажем вспомогательную лемму о сумме ряда.

|statement= <tex dpi = "160"> {\sum_{h = 1}^\infty \limits}\frac{h}{dD^h} = \frac{dD}{(d D - 1)^2} . </tex>

Обозначим за <tex> S</tex> сумму ряда. Заметим, что<tex dpi = "160"> \frac{nh}{dD^nh} = \frac{1}{dD} \cdot \frac{n - 1}{d D ^{n - 1}} + \frac{1}{dD^n}. </tex>

<tex dpi = "160">{\sum_{n = 1}^\infty \limits}\frac{1}{d^n} - </tex> {{---}} это сумма бесконечной убывающей геометрической прогрессии, ее сумма и она равна <tex dpi = "160"> \frac{\frac{1}{dD}}{1 - \frac{1}{dD}} = \frac{1}{d D - 1}. </tex>

Получаем <tex> S </tex> <tex dpi = "160" >= \frac{1}{dD}</tex> <tex>\cdot S+</tex> <tex dpi = "160" > + \frac{1}{d D - 1}. </tex> Откуда <tex> S</tex> <tex dpi = "160"> = \frac{dD}{(d D - 1)^2}. </tex>

Получаем время работы Подставляя в нашу формулу результат леммы, получаем <tex> N</tex> <tex dpi = "160">\cdot (\frac {D}{D - 1})^2 </tex> <tex> < 5 \cdot N </tex> <tex>=O(N). </tex>