Вы представляете кучу как массив.Два элемента под i -ым элементом находятся в позициях 2*i+1 и 2*i+2.Если массив содержит n элементов, тогда, начиная с конца, возьмите каждый элемент и дайте ему «упасть» в нужное место в куче.Это O(n) для запуска.
Почему?Ну для n/2 элементов нет детей.Для n/4 есть поддерево высоты 1. Для n/8 есть поддерево высоты 2. Для n/16 поддерево высоты 3. И так далее.Итак, мы получаем серию n/2<sup>2</sup> + 2*n/2<sup>3</sup> + 3*n/2<sup>4</sup> + ... = (n/2)(1 * (1/2 + 1/4 + 1/8 + . ...) + (1/2) * (1/2 + 1/4 + 1/8 + . ...) + (1/4) * (1/2 + 1/4 + 1/8 + . ...) + ...) = (n/2) * (1 * 1 + (1/2) * 1 + (1/4) * 1 + ...) = (n/2) * 2 = n.Таким образом, общее число «посмотрим, нужно ли мне упасть еще на один, и если да, то каким способом я упаду? Сравнения составляют n. Но вы округлились от дискретизации, так что вы всегда получаете менее n наборы свопов, которые нужно выяснить. Каждое из которых требует не более 3 сравнений. (Сравните корень с каждым потомком, чтобы увидеть, нужно ли ему падать, затем потомками друг с другом, если корень был больше, чем у обоих потомков.)