Пирамидальная сортировка: разобрать кучу на месте

Если ты умеешь сортировать пирамидально (построить макс-кучу, потом n−1 раз «корень в конец + просеять») и знаешь, почему это Θ(n·log n) на месте, но не устойчиво, листай до «Теперь сам».

Как думаешь, как превратить кучу в отсортированный массив

Куча даёт максимум за O(1) - он в корне. Идея сортировки напрашивается: доставай максимумы по одному. Достал наибольший - куда его деть, чтобы не заводить второй массив? В КОНЕЦ этого же массива, на место, которое куче больше не нужно: куча ужмётся на один, а освободившийся хвост будет копить отсортированное. Достаём максимумы - и они ложатся в конец по убыванию извлечения, то есть массив выстраивается по возрастанию. Всё на месте, без буфера. Это и есть пирамидальная сортировка.

На что это похоже

Турнир, из которого чемпиона после победы сажают в «зал славы» - крайнее правое кресло. Ушёл чемпион - на вершину поднимают сильнейшего из оставшихся (быстрая перестройка пирамиды), он становится новым чемпионом и садится в кресло левее прежнего. Зал славы заполняется справа налево - сильнейший дальше всех справа. Когда турнир опустеет, зал славы - это все участники по возрастанию силы слева направо. Ни одного лишнего стула рядом не понадобилось: чемпионы садятся в те же кресла, что освобождает турнир.

Механизм: построить кучу, потом снимать максимумы в конец

1. построить макс-кучу из всего массива          (Θ(n))
2. для end от n−1 до 1:
       поменять a[0] и a[end]   # максимум - в конец, на финальное место
       уменьшить кучу до end    # хвост [end..n−1] уже отсортирован
       просеять_вниз(0, end)    # новый корень - на место, O(log n)

После шага 1 максимум в a[0]. На каждой итерации шага 2 мы кладём текущий максимум в конец активной кучи и восстанавливаем свойство одним просеиванием нового корня. Активная куча тает слева, отсортированный хвост растёт справа - пока не останется один элемент, уже наименьший, на месте 0.

Правило

Пирамидальная сортировка: (1) за Θ(n) построить макс-кучу; (2) n − 1 раз поменять корень (максимум) с последним элементом кучи, ужать кучу на один и просеять новый корень вниз за O(log n). Отсортированное копится в конце массива. Итог - Θ(n·log n) в ЛЮБОМ случае, НА МЕСТЕ (память O(1)). Плата - неустойчивость. Это единственная из наших сортировок, дающая и гарантию n·log n, и работу на месте одновременно.

Разбор: почему это Θ(n·log n)

Складываем два шага. Построение кучи - Θ(n) (прошлый урок). Затем n − 1 извлечений максимума, каждое - это обмен (O(1)) плюс просеивание нового корня вниз, а просеивание стоит O(log n) (высота дерева). Значит второй шаг - (n−1) · O(log n) = O(n·log n). Всего Θ(n) + O(n·log n) = O(n·log n). Заметь: этот потолок верен ДЛЯ ЛЮБОГО входа - в отличие от быстрой сортировки, у пирамидальной нет худшего случая Θ(n²), потому что высота кучи всегда log n, как бы ни были расставлены данные. Именно поэтому её используют как «страховку»: промышленная быстрая сортировка (introsort - её разберём в последней главе раздела) переключается на пирамидальную, когда рекурсия уходит слишком глубоко, - чтобы гарантировать n·log n даже в худшем случае.

Разбор: почему на месте, но не устойчива

На месте - потому что и построение кучи, и извлечения переставляют элементы прямо внутри исходного массива: активная куча и отсортированный хвост делят один и тот же массив, граница между ними просто сдвигается. Дополнительной памяти нужно O(1) (пара переменных), не считая стека - а его нет, если просеивание написать циклом, а не рекурсией. Неустойчива она потому, что просеивание меняет местами далёкие элементы (корень с последним, узел с ребёнком), и равные легко перепрыгивают друг друга - их исходный порядок теряется, как и у быстрой сортировки. Так что пирамидальная - это «гарантия n·log n + на месте, но без устойчивости»; если нужна устойчивость, берут слияние.

Что ломается без этого

Первая ошибка - при извлечении просеивать вниз в ГРАНИЦАХ всей кучи, а не ужатой: просеивание должно знать новый (уменьшенный) размер, иначе оно затянет уже уложенный в конец максимум обратно в кучу, и сортировка сломается. Вторая - строить МИН-кучу и удивляться, что массив выходит отсортированным по УБЫВАНИЮ: для возрастания нужна макс-куча (максимум уходит в конец). Третья - ждать устойчивости: её нет. Четвёртая - писать просеивание рекурсией и потерять преимущество O(1) памяти (появится стек глубины log n); на практике его пишут циклом.

Зачем это в работе

Пирамидальная сортировка ценна одним редким сочетанием: гарантия n·log n при ЛЮБОМ входе И работа на месте (без Θ(n) буфера, как у слияния). Поэтому её берут как страховку от худшего случая быстрой сортировки - в introsort (стандартная быстрая сортировка в C++ и не только) она включается при слишком глубокой рекурсии, спасая от Θ(n²). Её же выбирают там, где память в дефиците, а гарантия важна (встроенные системы, ядра ОС). На практике она обычно чуть медленнее быстрой сортировки по КОНСТАНТЕ (прыжки по массиву при просеивании плохо ложатся на кеш - привет локальности памяти из раздела про массивы), но её n·log n непробиваем. А сама куча под ней - это очередь с приоритетом, рабочая лошадка Дейкстры, Хаффмана и планировщиков.

Теперь сам

После построения макс-кучи из пяти элементов первый шаг извлечения меняет a[0] и a[4]. Что теперь на месте 4, что стало корнем и что делают дальше? Почему всего таких шагов n − 1, а не n?