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

Фотография озера Иссык в 120 пикселей шириной — это 9600 пикселей, а если читать их строка за строкой, то обычный массив. Отсортируем его по яркости пирамидальной сортировкой и будем после каждого шага рисовать массив снова как картинку. Сначала из пикселей строится куча, и фотография почти не меняется. Потом самый яркий пиксель кучи раз за разом уходит в конец массива, и картинка стекает в градиент, от тёмного сверху к светлому снизу.

На построение кучи ушло 13 841 сравнение, и после него 6828 пикселей из 9600 стоят там же, где стояли. Вторая половина массива — листья дерева, а листу тонуть некуда: его сдвигает только родитель, который сам тонет. Всё остальное время — 206 тысяч сравнений из 220 301 — заняла вторая фаза: 9599 раз вынуть наибольший и починить кучу. Нажмите на любой пиксель внизу картинки: появится его путь к вершине кучи. Первый шаг к родителю перебрасывает через полфотографии, следующий — через четверть, и так до левого верхнего угла. Об этих прыжках речь пойдёт в разделе о скорости.

Идея

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

Всё держится на устройстве двоичной кучи: полное двоичное дерево, разложенное по массиву без указателей, — дети ячейки i лежат в ячейках 2i + 1 и 2i + 2, и каждый родитель не меньше своих детей. Для сортировки по возрастанию нужна куча с наибольшим наверху: вершина уходит в конец массива, и хвост собирается от больших к меньшим, справа налево. Ровно поэтому на фото самые яркие пиксели появляются первыми, в правом нижнем углу.

Обе фазы сводятся к одной операции — просеиванию вниз. Элемент, который стоит выше, чем ему положено, меняют с большим из детей, пока он не окажется не меньше обоих детей или не дойдёт до листа.

1. Построение. Просеять вниз каждый узел, у которого есть дети, от последнего такого узла (ячейка ⌊n/2⌋ − 1) к корню. Когда очередь доходит до узла, оба его поддерева уже кучи, и после просеивания кучей становится и его поддерево. Этот способ предложил Роберт Флойд, и он стоит меньше 2n сравнений — доказательство в статье о куче.
2. Извлечение. Для end = n − 1, …, 1: поменять местами a[0] и a[end], теперь a[end] на своём окончательном месте; куча — a[0:end], и на её вершине чужой элемент; просеять его вниз.

По шагам

Те же шестнадцать сильнейших землетрясений 2025 года, на которых работают статьи о слиянии и быстрой сортировке. Сверху массив нарисован деревом, снизу — как есть, ячейка за ячейкой. Следите за тем, откуда приходит новая вершина после каждого извлечения.

Построение кучи обошлось в 24 сравнения, извлечения — в 55, всего 79. Слиянию на тех же данных понадобилось 46 сравнений, быстрой сортировке со случайным опорным — 98. А теперь посмотрите на извлечения внимательнее. Новая вершина всякий раз приходит из последней ячейки кучи, то есть с самого нижнего этажа, — а там лежит что-то из самых маленьких. Ей почти всегда предстоит тонуть до дна, и на каждом этаже она платит два сравнения: сначала дети между собой, потом больший ребёнок с ней. На этом наблюдении держится главное ускорение пирамидальной сортировки, к нему мы вернёмся ниже.

Почему n log n на любом входе

Здесь важно слово «любом». Худшего входа у пирамидальной сортировки нет — но нет и лучшего. Сортировка вставками на почти упорядоченном массиве делает около n сравнений, Timsort находит готовые прогоны, а пирамидальной сортировке всё равно, что ей дали. Вот три входа из первой сцены, все из одних и тех же пикселей:

Массив, упорядоченный по убыванию, уже куча: построение только убеждается в этом, 9599 = n − 1 сравнений и ни одного обмена. Но вторая фаза всё равно разбирает кучу до основания, и разница между лучшим и худшим входом — восемь процентов. Отсортированный по возрастанию массив, который быстрая сортировка с первым опорным превращает в квадрат, здесь обходится всего на 6 % дороже фотографии.

Сортировку, которая замечает готовый порядок, построил на кучах Эдсгер Дейкстра в 1981 году — smoothsort. Вместо одной двоичной кучи она держит лес куч, размеры которых — числа Леонардо (1, 1, 3, 5, 9, 15, …, каждое на единицу больше суммы двух предыдущих), и на упорядоченном массиве работает за O(n), а в худшем случае — за O(n log n), без лишней памяти. Она заметно сложнее, и в жизни встречается редко; один из примеров — qsort в библиотеке musl.

Почти половина сравнений лишняя

Вернёмся к наблюдению из второй сцены. После обмена вершина кучи — бывший последний лист, один из самых маленьких элементов. В куче половина узлов — листья, четверть — их родители, поэтому случайный маленький элемент почти наверняка утонет на самое дно или на этаж выше. А обычное просеивание на каждом этаже по дороге сравнивает его с большим ребёнком — проверяет, не пора ли остановиться, хотя почти всегда не пора.

Отсюда просеивание снизу вверх. Сначала вовсе не смотрим на тонущий элемент: спускаемся от вершины до листа, всякий раз переходя к большему из детей, — это одно сравнение на этаж. Получился путь, вдоль которого элементы не возрастают; тонущий элемент окажется где-то на нём. Ищем его место, поднимаясь от листа вверх: обычно хватает одного-двух сравнений, ведь место почти у дна. Потом все элементы пути от вершины до найденного места поднимаются на этаж, а тонущий встаёт на освободившееся место. Обмены те же самые, что у обычного просеивания, порядок на выходе тот же, а сравнений на 40 % меньше.

Переключите в первой сцене просеивание на «снизу вверх». На фотографии это 132 979 сравнений вместо 220 301 — 1,05 n log₂ n вместо 1,73. Почти вся экономия приходится на вторую фазу. На построении новый приём даже проигрывает: 17 978 сравнений против 13 841. Там просеивается узел из середины массива, обычный, не из самых маленьких, и он нередко останавливается сразу, а спуск до листа всё равно тратит сравнения на каждом этаже.

Дональд Кнут приводит этот приём в упражнении к разделу 5.2.3 третьего тома «Искусства программирования», где разобрана пирамидальная сортировка, и приписывает его Флойду. Подробно его разобрал Инго Вегенер: в статье 1993 года с говорящим названием «BOTTOM-UP-HEAPSORT, новый вариант HEAPSORT, который в среднем обгоняет QUICKSORT (если n не очень мало)» он показал, что сравнений в среднем около n log₂ n, а в худшем случае не больше 1,5 n log₂ n + O(n). Обгоняет — по числу сравнений: быстрой сортировке со случайным опорным нужно в среднем около 1,39 n log₂ n.

С 2019 года так сортирует ядро Linux: функция sort() из lib/sort.c — пирамидальная сортировка с просеиванием снизу вверх. Автор изменения, Джордж Спелвин, оценил выигрыш в сообщении к нему: было в среднем 2n log₂ n − 3n сравнений, стало n log₂ n + 0,37n. В ядре сравнение — вызов функции по указателю, а после защит от атак Spectre такие вызовы стали дорогими, и сэкономленное сравнение стоит заметно больше, чем пара лишних шагов по массиву.

Код

Пирамидальная сортировка в одной функции: внутренняя функция просеивания и два цикла. Счётчик сравнений разбит на две фазы — это те же 24 и 55, что в сцене с землетрясениями.

Неустойчивость видна сразу: из четырёх землетрясений силой 7,4 ни одно не осталось на своём месте среди равных. Обмен вершины с концом кучи переносит элемент через весь массив, мимо равных ему, и никакого порядка среди равных эта сортировка не помнит:

  7.4: 07-20 10-10 05-02 09-13  <- out of date order

Вторая программа — первая сцена целиком: она читает ту же фотографию в песочнице, сортирует её пиксели обоими способами просеивания на трёх входах и проверяет, что результаты совпали пиксель в пиксель.

Сколько это стоит

По таблице пирамидальная сортировка выглядит лучшей из трёх: гарантия слияния и память быстрой. Но замер говорит другое. Ниже — Python и Go, случайные числа, пирамидальная сортировка в двух вариантах, быстрая из статьи о ней и встроенная.

На Go, пока массив небольшой, пирамидальная идёт вровень с быстрой: на 16 тысячах чисел у них одно и то же время. Дальше она отстаёт и тем сильнее, чем больше массив: на 256 тысячах и на миллионе — в 1,2 раза, на четырёх миллионах — в 2,4. Сравнений у неё больше, но их отношение к числу сравнений быстрой сортировки от n почти не зависит. Растущее отставание — от памяти.

Быстрая сортировка читает массив подряд: два указателя идут навстречу, и процессор заранее подкачивает в кэш следующие ячейки. Пирамидальная прыгает: из ячейки i в 2i + 1, из неё в 4i + 3, и на нижних этажах каждый шаг уводит на мегабайты дальше. Нажмите в первой сцене на пиксель в нижнем ряду: его путь к вершине пролетает через всю картинку, и соседи по дереву в памяти почти никогда не соседи. Пока массив целиком лежит в кэше процессора, прыжки бесплатны; когда перестаёт помещаться, почти каждый шаг вниз по дереву — промах кэша. Об этом подробно — в статье о коде, который дружит с кэшем.

Просеивание снизу вверх на этих замерах не помогает: сравнить два числа float64 стоит меньше, чем лишний проход по пути, и на Go оно медленнее обычного в 1,3–1,8 раза. Экономия сравнений окупается, когда сравнение дорогое: вызов функции по указателю, как в ядре Linux, сравнение строк или записей по нескольким полям. На Python обе пирамидальные сортировки медленнее быстрой в полтора-три раза: там время уходит на интерпретатор, и до промахов кэша дело не доходит, а встроенная сортировка, написанная на C, обгоняет всех в 10–40 раз.

Где она работает

Страховка быстрой сортировки. Быстрая сортировка хороша всем, кроме худшего случая. Introsort Дэвида Массера (1997) — быстрая сортировка, которая следит за глубиной рекурсии и, если та превысила предел, досортировывает оставшийся кусок пирамидальной. Так устроена std::sort в libstdc++: предел глубины — 2⌊log₂ n⌋, а запасной путь — функция частичной сортировки, которая на всём куске и есть пирамидальная сортировка. Так же устроен Array.Sort в .NET: в документации сказано, что при числе разбиений больше 2 log n метод переходит на пирамидальную сортировку. В Go с версии 1.19 сортирует pdqsort: он считает неудачные разбиения, где меньшая часть короче восьмой доли куска, и после ⌊log₂ n⌋ + 1 таких разбиений тоже зовёт пирамидальную. В Rust sort_unstable основана на ipnsort, которая по документации соединяет быстрый средний случай быстрой сортировки с быстрым худшим случаем пирамидальной. В Java двухопорная быстрая сортировка массивов чисел, переписанная к версии 14, при слишком глубокой рекурсии тоже переходит на пирамидальную. На обычных данных этот запасной путь не срабатывает никогда; он нужен против данных, подобранных противником, — их строит, например, атака Макилроя.

Где нельзя ни рекурсии, ни памяти. В ядре операционной системы стек мал, выделять память во время сортировки нежелательно, а время должно быть предсказуемым. Поэтому sort() в ядре Linux — пирамидальная сортировка, и в комментарии к коду прямо сказано, почему не быстрая: у той худший случай n², который можно вызвать нарочно, и дополнительная память. То же годится для встроенных систем и для кода реального времени.

k лучших. Если нужен не весь порядок, а только k наибольших, пирамидальную сортировку останавливают после k извлечений: O(n + k log n). А std::partial_sort в C++ делает наоборот: держит кучу из k элементов и пропускает через неё остальные, а потом сортирует саму кучу. Это отдельная тема — статья «Top-k: k лучших».

История

Пирамидальная сортировка появилась в июне 1964 года в журнале Communications of the ACM: в разделе алгоритмов вышла короткая заметка Дж. У. Дж. Уильямса «Algorithm 232: Heapsort» с программой на Алголе. В ней появилась и сама куча — Уильямс описал её как полезную структуру саму по себе. Кучу он строил добавлением элементов по одному, за O(n log n). В декабре того же года Роберт Флойд напечатал в том же журнале «Algorithm 245: Treesort 3» — сортировку почти в том виде, в каком её пишут сейчас, с построением кучи снизу вверх за линейное время. Флойд и раньше публиковал сортировки деревом — первая, «Algorithm 113: Treesort», вышла в 1962 году, — и их можно считать шагами к пирамидальной. Рассказ об Уильямсе — в главе курса «Кто следующий».

Дальше у пирамидальной сортировки было два пути. Один — экономить сравнения: просеивание снизу вверх, описанное Кнутом со ссылкой на Флойда и разобранное Вегенером в 1990–1993 годах. Другой — замечать готовый порядок: smoothsort Дейкстры 1981 года. А в 1997 году Массер нашёл ей роль, в которой она работает до сих пор, — страховки внутри быстрой сортировки.

Задачи

В первой задаче сортировку остановили сразу после построения кучи, и надо понять, где в куче может оказаться k-й по величине элемент: это вопрос о свойстве кучи, а не о коде. Вторая — аккуратно реализовать просеивание снизу вверх и посчитать, сколько сравнений оно экономит.