|statement= Время работы этого алгоритма <tex> O(N) </tex>.
|proof=
Подсчитаем суммарное число операций за все время работы алгоритма. Пусть <tex> H </tex> высота дерева. Подсчитаю сумму, сколько нужно операций для перемещения Число вершин в лист. <tex dpi = "160"> \frac{N}{4} </tex> вершин опустятся на 1, высоте <tex dpi ="160"> \frac{N}{8} h</tex> опустятся на 2 и.т.д. Получим сумму в куче из n элементов не превосходит <tex dpi = "160"> \frac{N}{2} \cdot {\sum_{i = 1}^H \limits}left [ \frac{in}{2^i}.</tex> <tex dpi = "160"> {\sum_{i = 1}^H \limitsh}\frac{i}{2^i} = 4</tex> (известная сумма из математического анализа) Откуда получаем оценку <tex> O(N) right ] </tex>.
}}
Также можно обобщить на случай <tex> D-</tex> кучи. В этом случае время работы будет <tex dpi = "160">
