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

Понятия

Двоичная куча - почти полное двоичное дерево со свойством: родитель ≥ детей (макс-куча), поэтому максимум в корне. Хранится в МАССИВЕ: у узла i дети 2i+1 и 2i+2, родитель (i−1)//2 - без ссылок.

Просеивание вниз (sift-down) - восстановление свойства: меняем узел с бо́льшим ребёнком, пока он не станет ≥ детей. Идёт по высоте дерева - O(log n).

Построение кучи - просеивание вниз по узлам СНИЗУ ВВЕРХ (от n//2 − 1 до 0). Стоит Θ(n), а не Θ(n·log n): узлов высоты h около n/2^(h+1), сумма n·Σ h/2ʰ сходится к Θ(n).

Пирамидальная сортировка - построить макс-кучу, затем n − 1 раз: поменять корень (максимум) с последним элементом кучи, ужать кучу, просеять новый корень. Θ(n·log n) при любом входе, на месте, НЕ устойчива.

Очередь с приоритетом - структура «достать самый важный»; реализуется кучей.

Что унести

Куча - это компромисс между отсортированным и неотсортированным массивом: максимум под рукой (O(1)), а вставка и удаление максимума - O(log n). Свойство связывает только родителя с детьми; куча НЕ отсортирована.

Построение за Θ(n) - важный факт: грубая оценка n × log n завышена, потому что почти все узлы у дна и просеиваются почти никуда. Ряд Σ h/2ʰ сходится к константе. Направление решает: sift-down снизу вверх - Θ(n); добавление по одному (sift-up) - Θ(n·log n).

Пирамидальная сортировка сравнительно с другими n·log n:

Уникальность пирамидальной - гарантия n·log n И работа на месте одновременно. Отсюда её роль страховки в introsort (переключение при глубокой рекурсии быстрой) и выбор при дефиците памяти. На практике по КОНСТАНТЕ чуть медленнее быстрой (прыжки по массиву плохо ложатся на кеш - локальность памяти).

Ловушки джокера

Перепутал формулы индексов (родитель как i//2 вместо (i−1)//2). Переходы промахиваются, куча ломается молча.

При просеивании меняешь узел с любым ребёнком, а не с большим. Наверх поднимется не максимум, свойство не восстановится.

Строишь кучу сверху вниз (с корня). Опираешься на непочиненные поддеревья - куча не соберётся. Начинай с n//2 − 1.

Просеиваешь в границах всей кучи при извлечении, а не ужатой. Затянешь уже уложенный максимум обратно.

Считаешь построение кучи за Θ(n·log n). Оно Θ(n) - плата за лишний log n на больших данных.

Проверь себя

Что такое свойство кучи и как она укладывается в массив?

Почему просеивание - O(log n), а построение кучи - Θ(n), а не Θ(n·log n)?

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

Почему она укладывается в O(n·log n) при любом входе и работает на месте?

Почему она не устойчива и где её берут как страховку?