Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за O ( n log n ) {displaystyle O(nlog n)} операций при сортировке n {displaystyle n} элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O ( 1 ) {displaystyle O(1)} ).
Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.
История создания
Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году.
Алгоритм
Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:
Удобная структура данных для сортирующего дерева — такой массив 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.