Пирамидальная сортировка (англ.Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за операций при сортировке элементов.[2] Алгоритм работает «на месте» — количество задействованной служебной памяти , то есть фиксированное[1].
2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем и , преобразовываем в сортирующее дерево. Затем переставляем и , преобразовываем в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда - упорядоченная последовательность.
Этот шаг требует операций.
Достоинства и недостатки
Достоинства:
Имеет доказанную оценку худшего случая .
Сортирует на месте, то есть требует всего дополнительной памяти (если дерево организовывать так, как показано выше).
Недостатки:
Неустойчив — для обеспечения устойчивости нужно расширять ключ.
На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти[1].
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К.Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 182—188. — ISBN 5-8459-0857-4.
Пирамидальная сортировка — подробное описание с иллюстрациями и примером реализации на C++. Приведён вывод оценок скорости работы алгоритма и измерение времени работы на реальной вычислительной системе.