Сортировка кучей :: Heap sort
Она же пирамидальная сортировка.
Алгоритм
Основная идея - ищем максимальный элемент в неотсортированной части массива и ставим его в конец этого подмассива. В поисках максимума подмассив перестраивается в так называемое сортирующее дерево (она же двоичная куча, она же пирамида), в результате чего максимум сам "всплывает" в начало массива. После этого перемещаем максимум в конец подмассива. Затем над оставшейся частью массива снова осуществляется процедура перестройки в сортирующее дерево с последующим перемещением максимума в конец подмассива.
Сортирующее (неубывающее) дерево - дерево у которого любой родитель не меньше чем каждый из его потомков. Если сортирующее дерево невозрастающее, то, соответственно, любой родитель не больше чем каждый из его потомков.
Сложность по времени
У алгоритма нет благоприятных и вырожденных случаев. При любом входящем массиве (даже если он почти отсортирован) сортировка имеет одну и ту же временную сложность - O(n log n).
Дополнительно
Сортировка кучей используется в целом ряде других алгоритмов сортировок.
Это как её непосредственные вариации:
- Тернарная пирамидальная сортировка
- Сортировка декартовым деревом
- Плавная сортировка
Так и гибридные алгоритмы:
Характеристики алгоритма
| Название | Сортировка кучей (Heap sort, Пирамидальная сортировка, Pyramid sort) | |
|---|---|---|
| Автор | J. W. J. Williams | |
| Год | 1964 | |
| Класс | Сортировки выбором | |
| Устойчивость | Нет | |
| Сравнения | Да | |
| Сложность по времени | Лучшая | O (n log n) |
| Средняя | ||
| Худшая | ||
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Пирамидальная сортировка
Реализация на различных ЯП