Пирамидальная сортировка

Пирамидальная сортировка — это сортировка выбором с лучшим способом найти наибольшее значение. Она держит неотсортированные значения в куче — дереве, хранящемся прямо в списке, где наибольшее значение всегда наверху. Чтобы снять его и восстановить кучу, нужно около log n шагов, а не полный просмотр.

Куча в виде двоичного дерева над теми же значениями в виде столбиков; наибольшее значение в корне переносится в конец списка
Куча в виде двоичного дерева над теми же значениями в виде столбиков; наибольшее значение в корне переносится в конец списка

Дерево внутри списка

Двоичная куча — это дерево, которому не нужны указатели. Позиция 0 — корень, а потомки позиции i — позиции 2i + 1 и 2i + 2, так что позиции 1 и 2 — потомки корня, позиции с 3 по 6 — следующий уровень, и так далее. Каждый уровень заполнен, кроме последнего, который заполняется слева. В max-куче каждый родитель не меньше своих потомков, поэтому наибольшее значение всегда в корне.

Просеивание вниз

Всю работу делает одна операция. Чтобы просеять значение вниз, сравните его с потомками. Если больший потомок больше значения, они меняются местами, и значение сравнивается с новыми потомками. Просеивание останавливается, когда ни один потомок не больше или когда значение достигает нижнего уровня. Так как в дереве всего около log₂ n уровней, просеивание требует не больше примерно 2 log₂ n сравнений.

Сначала куча, потом сортировка

Чтобы построить кучу, просейте вниз каждого родителя, от последнего обратно к корню. Каждое поддерево уже является кучей, прежде чем в него просеивается его родитель. Затем сортируйте: поменяйте корень, наибольшее значение, с последним значением кучи. Это значение теперь на своём окончательном месте. Куча стала на один элемент короче, а значение, попавшее в корень, просеивается вниз, чтобы её восстановить. Повторяйте, пока не останется одно значение.

Пример

Возьмём 5, 1, 4, 2, 8. При построении кучи 1 просеивается вниз под 8, затем 5 — под 8, и получается 8, 5, 4, 2, 1. Теперь 8 уходит в конец; 1 попадает в корень и просеивается вниз мимо 5 и 2: 5, 2, 4, 1 | 8. Затем 5 уходит в конец, а 1 просеивается мимо 4: 4, 2, 1 | 5, 8. Ещё два раунда завершают список: 1, 2, 4, 5, 8, после 12 сравнений и 10 обменов.

Сильные и слабые стороны

Пирамидальная сортировка занимает время, пропорциональное n log n, даже в худшем случае, и ей не нужна дополнительная память. Быстрая сортировка может замедлиться до n², а сортировке слиянием нужен буфер длиной со список, поэтому пирамидальная сортировка — надёжный запасной вариант: introsort, используемый в стандартной библиотеке C++, переключается на неё, когда разбиения быстрой сортировки идут плохо. На реальных компьютерах она обычно медленнее обеих, потому что прыгает между далёкими местами списка, и она неустойчива. J. W. J. Williams опубликовал пирамидальную сортировку вместе с двоичной кучей в 1964 году.

Попробуйте сами

Откройте приложение и нажмите «Шаг». Дерево над столбиками показывает кучу: просеиваемое значение выделено своим цветом, потомок, с которым оно сравнивается, подсвечен, а каждый обмен виден и в дереве, и на столбиках. Когда куча построена, смотрите, как корень уходит в конец, становится зелёным и исчезает из дерева.

Часто задаваемые вопросы

Какова временная сложность пирамидальной сортировки?

O(n log n) в лучшем, среднем и худшем случае. Построение кучи занимает O(n), а каждое из n − 1 извлечений — O(log n). Сортирует на месте с O(1) дополнительной памяти.

Чем пирамидальная сортировка отличается от сортировки выбором?

Обе раз за разом берут наибольшее (или наименьшее) из оставшихся значений. Сортировка выбором находит его полным просмотром неотсортированной части, каждый раз n сравнений. Пирамидальная сортировка держит неотсортированную часть в куче, где наибольшее значение уже наверху, а восстановление кучи стоит всего около log n сравнений.

Где ещё используется куча, кроме сортировки?

В очередях с приоритетом: куча сразу даёт наибольший (или наименьший) элемент и позволяет добавлять и удалять элементы примерно за log n шагов. Её используют планировщики задач, алгоритм Дейкстры (Dijkstra) для поиска кратчайшего пути и событийное моделирование.

Устойчива ли пирамидальная сортировка?

Нет. Перенос корня в конец перемещает значения на большие расстояния, поэтому равные значения могут поменяться местами.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать пирамидальную сортировку