Сравнения
Обмены
Извлечено

  • Просеивается вниз
  • Сравниваются
  • Обменяны
  • На месте

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

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

Пирамидальная сортировка (heapsort) читает список как двоичное дерево и перестраивает его в max-кучу, где каждый родитель не меньше своих потомков. Тогда наибольшее значение оказывается наверху. Переместите его в конец, где оно и останется, восстановите кучу и повторите. Приложение рисует кучу в виде дерева над столбиками, так что можно следить за каждым значением, пока оно просеивается вниз. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место. Дерево над столбиками показывает те же значения в виде кучи. Плитки считают сравнения, обмены и значения, извлечённые из кучи. Выберите число столбиков, начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.

Как это работает

  1. Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
  2. Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
  3. Следите за деревом: сначала каждый родитель просеивается вниз, пока куча не будет построена, затем корень переносится в конец, а куча уменьшается на один элемент.

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

Читайте список как дерево: у значения на позиции 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 в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор