Пирамидальная сортировка
Пирамидальная сортировка — это сортировка выбором с лучшим способом найти наибольшее значение. Она держит неотсортированные значения в куче — дереве, хранящемся прямо в списке, где наибольшее значение всегда наверху. Чтобы снять его и восстановить кучу, нужно около 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 в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать пирамидальную сортировку