Изменения
Нет описания правки
'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''Heapsort''') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча|двоичная куча]]. Это нестабильный алгоритм сортировки с гарантированным временем работы <tex>\ThetaO(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(0)''', предварительно уменьшив <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>n - 1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.
== Реализация ==
<tex>A</tex> {{---}} массив, который необходимо отсортировать; <tex>n</tex> {{---}} количество элементов в нем; '''build_heap(A)''' - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; '''sift_down(A, i, len)''' {{---}} процедура, которая просеивает вниз элемент <tex>A[i]</tex> в куче из <tex>len</tex> элементов, находящихся в начале массива <tex>A</tex>.
<pre>
heapsort(A)
swap(A[0], A[n - 1 - i]);
heap_size--;
sift_down(A, 0, heap_size);
</pre>
== Сложность ==
Операция '''sift_down''' работает за <tex>O(\log{n})</tex>. Всего цикл выполняется <tex>n - 1</tex> раз. Таким образом сложность сортировки кучей является <tex>O(n\log{n})</tex>.
== Пример ==
== Ссылки ==
*[http://ru.wikipedia.org/wiki/%D0%A19F%D0%BEB8%D1%80%D1D0%B0%D0%82BC%D0%B8%D1D0%80B4%D0%BEB0%D0%B2BB%D1%8C%D0%BABD%D0%B0_B0%D1%8F_%D1%81%D0%B2BE%D1%8B80%D0D1%B182%D0%BEB8%D1%80%D0%BE%D0%BC B2%D0%BA%D0%B0 Сортировка выбором кучей в русской википедии]*[http://en.wikipedia.org/wiki/Heapsort Сортировка кучей в английской википедии]
== Литература ==
