Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.[2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.
Этот раздел не завершён. |
Пирамидальная сортировка была предложена Дж. Уильямсом[en] в 1964 году.[1]
Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:
Удобная[источник не указан 841 день] структура данных для сортирующего дерева — такой массив Array
, что Array[0]
— элемент в корне, а потомки элемента Array[i]
являются Array[2i+1]
и Array[2i+2]
.
Алгоритм сортировки будет состоять из двух основных шагов:
1. Выстраиваем элементы массива в виде сортирующего дерева[источник не указан 841 день]:
при .
Этот шаг требует операций.
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) быстрее ( с меньшей константой) и не подвержена деградации на неудачных данных.
Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.
Алгоритм «сортировка кучей» активно применяется в ядре Linux.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .