Изменения

'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''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>, он встанет на свое своё место. Далее вызовем процедуру <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>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

*<tex>\mathrm{A}</tex> {{---}} массив, который необходимо отсортировать; *<tex>\mathrm{n}</tex> {{---}} количество элементов в нем; нём*<tex>build\_heapmathrm{buildHeap(A)} </tex> {{- --}} процедура, которая строит из передаваемого массива невозрастающую кучу для максимума в этом же массиве; *<tex>sift\_downmathrm{siftDown(A, i, len)} </tex> {{---}} процедура, которая просеивает вниз элемент <tex>\mathrm{A[i]} </tex> в куче из <tex>\mathrm{len} </tex> элементов, находящихся в начале массива <tex>\mathrm{A} </tex>. '''fun''' heapSort(A : '''list <preT>heapsort(A'''): build_heap buildHeap(A); heap_size heapSize = A.size; '''for ''' i = 0 '''to ''' n - 21 swap(A[0], A[n - 1 - i]); heap_size heapSize--; sift_down siftDown(A, 0, heap_sizeheapSize);</pre>

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

|[[Файл:heap6.png|155px|thumb|Четвертый Четвёртый проход]]

|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых четырех четырёх элементов

|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и четвертый четвёртый элементы

|style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых трех трёх элементов

|colspan=3|''Четвертый Четвёртый проход''