Пирамидальная сортировка ( англ. Heapsort , «Сортировка кучей» ) — алгоритм сортировки , работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за ${\displaystyle O(n\ln n)}$ операций при сортировке ${\displaystyle n}$ элементов. Алгоритм работает «на месте» — количество задействованной служебной памяти ${\displaystyle O(1)}$ , то есть фиксированное .

Может рассматриваться как усовершенствованная сортировка пузырьком , в которой элемент всплывает ( min-heap ) / тонет ( max-heap ) по многим путям.

Пирамидальная сортировка была предложена в 1963 году.

Алгоритм

Сортировка пирамидой использует бинарное сортирующее дерево . Сортирующее дерево — это такое дерево, у которого выполнены условия:

1. Каждый лист имеет глубину либо ${\displaystyle d}$ , либо ${\displaystyle d-1}$ , ${\displaystyle d}$ — максимальная глубина дерева.
2. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив ${\displaystyle a}$ , что ${\displaystyle a[0]}$ - элемент в корне, а потомки элемента ${\displaystyle a[i]}$ являются ${\displaystyle a[2i+1]}$ и ${\displaystyle a[2i+2]}$ .

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева ^{[ источник не указан 2651 день ]} :

${\displaystyle a[i]\geq a[2i+1]}$

${\displaystyle a[i]\geq a[2i+2]}$

при ${\displaystyle 0\leq i<n/2}$ .

Этот шаг требует ${\displaystyle O(n)}$ операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем ${\displaystyle a[0]}$ и ${\displaystyle a[n-1]}$ , преобразовываем ${\displaystyle a[0],a[1],\ ...,a[n-2]}$ в сортирующее дерево. Затем переставляем ${\displaystyle a[0]}$ и ${\displaystyle a[n-2]}$ , преобразовываем ${\displaystyle a[0],a[1],\ ...,a[n-3]}$ в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда ${\displaystyle a[0],a[1],\ ...,a[n-1]}$ - упорядоченная последовательность.

Этот шаг требует ${\displaystyle O(n\log n)}$ операций.

Достоинства и недостатки

Достоинства:

• Имеет доказанную оценку худшего случая ${\displaystyle O(n\log n)}$ .
• Сортирует на месте, то есть требует всего ${\displaystyle O(1)}$ дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки:

• Неустойчив — для обеспечения устойчивости нужно расширять ключ.
• На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
• На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти .
• Методу требуется доступ к произвольному элементу структуры ; не работает на связанных списках и других структурах памяти последовательного доступа.
• Не распараллеливается .

Сортировка слиянием при расходе памяти ${\displaystyle O(n)}$ быстрее ( ${\displaystyle O(n\log n)}$ с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших ${\displaystyle n}$ . На небольших ${\displaystyle n}$ (до нескольких тысяч) быстрее сортировка Шелла .

Применение

Пирамидальная сортировка активно применяется в ядре Linux .

Примечания

Литература

• Глава 6. Метод преобразования: Пирамиды и пирамидальная сортировка // — М. : , 2006. — С. 275—284. — 576 с. — ISBN 978-5-8459-0987-9
• Кормен, Т. , Лейзерсон, Ч. , Ривест, Р. , Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М. : Вильямс, 2005. — С. 182—188. — ISBN 5-8459-0857-4 .

Ссылки

• — подробное описание с иллюстрациями и примером реализации на C++ . Приведён вывод оценок скорости работы алгоритма и измерение времени работы на реальной вычислительной системе.
• — доходчивое описание с иллюстрациями и примером реализации на Pascal .
• от 20 сентября 2017 на Wayback Machine