- Просеивается вниз
- Сравниваются
- Обменяны
- На месте
Пирамидальная сортировка
Пирамидальная сортировка (heapsort) читает список как двоичное дерево и перестраивает его в max-кучу, где каждый родитель не меньше своих потомков. Тогда наибольшее значение оказывается наверху. Переместите его в конец, где оно и останется, восстановите кучу и повторите. Приложение рисует кучу в виде дерева над столбиками, так что можно следить за каждым значением, пока оно просеивается вниз. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место. Дерево над столбиками показывает те же значения в виде кучи. Плитки считают сравнения, обмены и значения, извлечённые из кучи. Выберите число столбиков, начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
- Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
- Следите за деревом: сначала каждый родитель просеивается вниз, пока куча не будет построена, затем корень переносится в конец, а куча уменьшается на один элемент.
Как работает пирамидальная сортировка
Читайте список как дерево: у значения на позиции i потомки стоят на позициях 2i + 1 и 2i + 2. Постройте max-кучу, просеивая вниз каждого родителя, начиная с последнего: пока значение меньше большего из своих потомков, они меняются местами. Когда в корне наибольшее значение, поменяйте его с последним значением кучи. Это значение теперь стоит на своём месте окончательно, куча стала на один элемент короче, а новый корень просеивается вниз, чтобы она снова стала кучей. Повторяйте, пока куча не опустеет.
Всегда n log n, на месте
В дереве около log₂ n уровней, поэтому каждое просеивание требует не больше примерно 2 log₂ n сравнений, а построение кучи — меньше 2n. В худшем случае пирамидальная сортировка делает около 2n log₂ n сравнений, без буфера: для 40 значений не больше 352. В отличие от быстрой сортировки, у неё нет плохих входных данных, а в отличие от сортировки слиянием, ей не нужна дополнительная память. На практике она обычно медленнее обеих, потому что прыгает по списку, и она неустойчива.
Часто задаваемые вопросы
Как работает пирамидальная сортировка?
Она превращает список в max-кучу — дерево, хранящееся в списке, где каждый родитель не меньше своих потомков. Затем она раз за разом переносит наибольшее значение из корня в конец кучи и просеивает новый корень вниз, чтобы восстановить кучу.
Что такое куча?
Полное двоичное дерево, хранящееся в списке без указателей: потомки позиции i — это позиции 2i + 1 и 2i + 2. В max-куче каждый родитель не меньше своих потомков, поэтому наибольшее значение всегда в корне, на позиции 0.
Почему куча строится быстро?
Большинство значений находятся в нижней части дерева и могут опуститься лишь на уровень-два. Если сложить работу по всем уровням, на всё построение уходит меньше 2n сравнений, а не n log n.
Устойчива ли пирамидальная сортировка?
Нет. Перенос корня в конец перемещает значения на большие расстояния, поэтому порядок равных значений может измениться.
Отправляются ли куда-нибудь мои числа?
Нет. Сортировка работает в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор