Изменения

'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''Heapsort''') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча|двоичная куча]]. Это нестабильный неустойчивый алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.

Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с <tex>A[n - 1]</tex>, он встанет на свое место. Далее вызовем процедуру '''sift_down<tex>sift\_down(0)'''</tex>, предварительно уменьшив <tex>heap\_size</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\_size</tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

<tex>A</tex> {{---}} массив, который необходимо отсортировать; <tex>n</tex> {{---}} количество элементов в нем; '''build_heap<tex>build\_heap(A)''' </tex> - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; '''sift_down<tex>sift\_down(A, i, len)''' </tex> {{---}} процедура, которая просеивает вниз элемент <tex>A[i]</tex> в куче из <tex>len</tex> элементов, находящихся в начале массива <tex>A</tex>.

Операция '''sift_down''' <tex>sift\_down</tex> работает за <tex>O(\log{n})</tex>. Всего цикл выполняется <tex>(n - 1)</tex> раз. Таким образом сложность сортировки кучей является <tex>O(n\log{n})</tex>.

|[[Файл:Документ1heap1.png|120px180px|thumb|Строим кучу]] |[[Файл:Документ2heap2.png|120px180px|thumb|Первый проход]] |[[Файл:Документ3heap3.png|120px180px|thumb|Строим новую кучу]]

|[[Файл:Документ4heap4.png|120px180px|thumb|Второй проход]] |[[Файл:Документ5heap5.png|120px180px|thumb|Третий проход]] |[[Файл:Документ6heap6.png|120px180px|thumb|Четвертый проход]]