Пирамидальная сортировка

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за O ( n log ⁡ n ) {displaystyle O(nlog n)} операций при сортировке n {displaystyle n} элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O ( 1 ) {displaystyle O(1)} ).

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

История создания

Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году.

Алгоритм

Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:

Каждый лист имеет глубину либо d {displaystyle d} , либо d − 1 {displaystyle d-1} , d {displaystyle d} — максимальная глубина дерева.

Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив Array, что Array[0] — элемент в корне, а потомки элемента Array[i] являются Array[2i+1] и Array[2i+2].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева:

Array [ i ] ≥ Array [ 2 i + 1 ] {displaystyle { ext{Array}}[i]geq { ext{Array}}[2i+1]}

Array [ i ] ≥ Array [ 2 i + 2 ] {displaystyle { ext{Array}}[i]geq { ext{Array}}[2i+2]}

при 0 ≤ i < n / 2 {displaystyle 0leq i<n/2} .

Этот шаг требует O ( n ) {displaystyle O(n)} операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[0] и Array[n-1], преобразовываем Array[0], Array[1], … , Array[n-2] в сортирующее дерево. Затем переставляем Array[0] и Array[n-2], преобразовываем Array[0], Array[1], … , Array[n-3] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[0], Array[1], … , Array[n-1] — упорядоченная последовательность.

Этот шаг требует O ( n log ⁡ n ) {displaystyle O(nlog n)} операций.

Достоинства и недостатки

Достоинства

• Имеет доказанную оценку худшего случая O ( n ⋅ log ⁡ n ) {displaystyle O(ncdot log n)} .
• Сортирует на месте, то есть требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

• Неустойчив — для обеспечения устойчивости нужно расширять ключ.
• На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
• На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
• Методу требуется «мгновенный» прямой доступ; не работает на связанных списках и других структурах памяти последовательного доступа.
• Не распараллеливается.

Сортировка слиянием при расходе памяти O(n) быстрее ( O ( n ⋅ log ⁡ n ) {displaystyle O(ncdot log n)} с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

Применение

Алгоритм «пирамидальная сортировка» активно применяется в ядре Linux.