Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.[2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.
Содержание |
Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году.[1]
Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево — это такое двоичное дерево, у которого выполнены условия:
Удобная структура данных для сортирующего дерева — такой массив Array
, что Array[1]
— элемент в корне, а потомки элемента Array[i]
— Array[2i]
и Array[2i+1]
.
Алгоритм сортировки будет состоять из двух основных шагов:
1. Выстраиваем элементы массива в виде сортирующего дерева:
при .
Этот шаг требует операций.
2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1]
и Array[n]
, преобразовываем Array[1]
, Array[2]
, … , Array[n-1]
в сортирующее дерево. Затем переставляем Array[1]
и Array[n-1]
, преобразовываем Array[1]
, Array[2]
, … , Array[n-2]
в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1]
, Array[2]
, … , Array[n]
— упорядоченная последовательность.
Этот шаг требует операций.
Достоинства
Недостатки
Сортировка слиянием при расходе памяти O(n) быстрее ( с меньшей константой) и не подвержена деградации на неудачных данных.
Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.
Алгоритмы сортировки | |
---|---|
Теория |
Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя |
Алгоритмы |
Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная |
Пирамидальная сортировка паскаль пример, пирамидальная сортировка рисунок.
Сивера, Евангелический приют для сирот, Категория:Музеи, основанные в 1715 году, Список синглов № 1 в США в 1994 году (Billboard).