Число вершин на высоте <tex>h</tex> в куче из <tex>n</tex> элементов не превосходит <tex dpi = "160"> \left \lceil \frac{n}{2^h} \right \rceil </tex>. Высота кучи не превосходит <tex> \log_{2} n </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит <tex dpi = "160"> \sum_{h = 1}^H \limits\frac{n}{2^h}</tex> <tex dpi = "150"> \cdot h </tex> <tex dpi = "160">= n \cdot {\sum_{h = 1}^H \limits}\frac{h}{2^h}. </tex>
<tex dpi = "160"> {\sum_{h = 1}^\infty \limits}\frac{h}{2^h} = 2 </tex> (известная сумма из матанализа)
Обозначим сумму ряда за Далее, будет подсчитана эта сумма в общем виде. Получаем оценку <tex> S O(N) </tex>. }}Также можно обобщить на случай <tex> d-</tex> кучи {{Определение | definition ='''<tex>d- </tex> Заметим чтокуча''' {{---}} это куча в которой не 2 потомка,а <tex> d </tex> потомков). }}
<tex dpi = "160"> \frac{n}{2^n} = \frac{1}{2} \cdot \frac{n - 1}{2 ^{n - 1}} + \frac{1}{2^n} </tex> Получается <tex> S = \frac{1}{2} \cdot S + 1 </tex> (так как <tex>n >0</tex>). Получаем, что сумма ряда равна 2.Откуда и получаем оценку <tex> O(N) </tex>. }}Также можно обобщить на случай <tex> d-</tex> кучи <tex>(d- </tex> куча это куча в которой не 2 потомка, а <tex> d </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>
Здесь появился множитель <tex> d </tex> из-за того, что поиск минимума в sift_down происходит за <tex> d </tex>.
