Изменения

Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с <tex>A[n - 1]</tex>, он встанет на свое место. Далее вызовем процедуру <tex>sift\_downmathrm{siftDown(0)} </tex>, предварительно уменьшив <tex>heap\_sizemathrm{heapSize} </tex> на <tex>1</tex>. Она за <tex>O(\log{n})</tex> просеет <tex>A[0]</tex> на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с <tex>A[0]</tex> по <tex>A[n - 2]</tex>, а элемент <tex>A[n-1]</tex> находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с <tex>A[n - 1]</tex>, а с <tex>A[n-2]</tex>. Делая аналогичные действия, пока <tex>heap\_sizemathrm{heapSize} </tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.