Heap Sort

Проблема

Быстрая сортировка в среднем очень быстра, но в худшем случае деградирует до O(n²), а сортировка слиянием гарантирует O(n log n), но требует O(n) дополнительной памяти. Нужен алгоритм с гарантированной асимптотикой O(n log n) в худшем случае, который при этом сортирует на месте, используя лишь O(1) дополнительной памяти.

Решение

Массив интерпретируется как бинарная куча (heap) - дерево, хранящееся прямо в массиве, где родитель элемента с индексом i находится по индексу (i-1)/2, а дети - по 2i+1 и 2i+2. Сначала массив превращается в max-heap - куча, где родитель всегда не меньше своих детей, то есть наибольший элемент оказывается в корне (индекс 0). Затем корень (максимум) меняется местами с последним элементом кучи, куча «сжимается» на один элемент, и просеивание (sift down) восстанавливает свойство кучи для нового корня. Шаг повторяется, пока куча не опустеет - так весь массив оказывается отсортирован на месте.

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

Проследим построение кучи на конкретном массиве [4, 10, 3, 5, 1] (n = 5). Родительские узлы - индексы 1 и 0. Просеивание индекса 1 (значение 10, дети 5 и 1) ничего не меняет - 10 уже больше обоих детей. Просеивание индекса 0 (значение 4, дети 10 и 3) находит, что левый ребёнок 10 больше - происходит обмен, массив становится [10, 4, 3, 5, 1], а узел 4 просеивается дальше вниз на позицию 1, обмениваясь с 5: итоговая куча - [10, 5, 3, 4, 1], построена всего за 2 обмена.

Наивная оценка фазы построения кучи - «n/2 узлов, каждый просеивается за O(log n)» - даёт O(n log n), но это завышенная граница. Для n = 16 наивная оценка предсказывает 16/2 * log₂16 = 32 сравнения, а фактический подсчёт даёт всего 24 сравнения. При n = 128 разрыв ещё заметнее: наивная граница - 448, фактическое число - 227, почти вдвое меньше.

Причина разрыва - распределение узлов по уровням дерева. Половина всех узлов - листья (просеивание стоит 0), четверть - на предпоследнем уровне (просеивание стоит O(1)), и так далее: чем глубже просеивание, тем меньше узлов его выполняют. Сумма n * Σ(k / 2^k) по всем уровням k сходится к константе, а не растёт с log n, что и даёт точную асимптотику O(n) для всей фазы построения.

Фаза извлечения ведёт себя иначе: там просеивание почти всегда идёт от корня, то есть почти всегда стоит полные O(log n) шагов, и повторяется n раз - отсюда её честные O(n log n). На полном прогоне сортировки массива [10, 9, ..., 1] (n = 10) фаза построения делает всего 9 сравнений и 0 обменов (массив уже частично похож на кучу по структуре), а вся сортировка целиком - 35 сравнений и 12 обменов.

Концепцию хранения бинарного дерева в массиве и первый алгоритм извлечения из него по одному элементу описал Дж. У. Дж. Уильямс (J. W. J. Williams) в статье 1964 года, представив структуру данных «куча» (heap) и назвав сам метод сортировки heapsort. В том же году Роберт Флойд (Robert W. Floyd) предложил более быстрый способ построения кучи снизу вверх - именно тот алгоритм из O(n) сравнений, что реализован здесь, вместо построения кучи последовательными вставками за O(n log n).

На случайном массиве из 16 элементов полная сортировка совершает 80 сравнений и 37 обменов - примерно 5 сравнений на элемент, что отражает 2 log₂16 = 8 как верхнюю границу глубины дерева, умноженную на количество извлечений. Эти числа растут вместе с n предсказуемо и без всплесков - в этом и состоит гарантия worst-case O(n log n), не зависящая от исходного порядка входных данных.

Итог: пирамидальная сортировка не выигрывает у quicksort по числу сравнений на типичных данных, но платит за свою гарантию именно тем, что её работа не зависит от структуры входа - build-heap стоит O(n) благодаря геометрической концентрации узлов у листьев, а extraction честно стоит O(n log n), и обе фазы вместе дают одну и ту же асимптотику при любом порядке элементов.

Нюансы выбора

Библиотечные и системные сортировки, требующие гарантий - когда нельзя допустить деградацию до O(n²) на враждебных или структурированных входных данных, а лишняя память для merge sort недоступна.

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

Против merge sort - если O(1) дополнительной памяти критичен (встраиваемые системы, работа с очень большими массивами на месте), а неустойчивость сортировки не имеет значения для задачи.

Для top-k выборки без полной сортировки - построить кучу за O(n) и извлечь только k наибольших элементов за O(k log n), не досортировывая оставшуюся часть массива до конца.

Примеры в коде

J. W. J. Williams, «Algorithm 232 - Heapsort» (Communications of the ACM, 1964) - оригинальная публикация, представившая структуру «куча» и метод сортировки на её основе.

Robert W. Floyd, «Algorithm 245 - Treesort 3» (Communications of the ACM, 1964) - статья того же года, предложившая быстрое построение кучи снизу вверх за O(n) сравнений вместо O(n log n).

Планировщики задач операционных систем используют структуру «куча» напрямую как очередь с приоритетом для выбора следующего процесса к исполнению - тот же механизм извлечения, что и в heapsort, но без финальной сортировки.

Реализации std::priority_queue в C++ и heapq в Python используют тот же алгоритм sift-down/sift-up для поддержания кучи в структурах данных, встроенных в стандартные библиотеки этих языков.

Когда применять

• Когда нужна гарантия O(n log n) в худшем случае и мало памяти - например, во встраиваемых системах или в системном коде, где непредсказуемое поведение quicksort недопустимо.
• Как строительный блок для других алгоритмов и структур данных: очередь с приоритетом, алгоритм Дейкстры, top-k выборка через частично отсортированную кучу.

Примеры из практики

• Introsort (используется в C++ std::sort) начинает с быстрой сортировки, но переключается на heapsort, если рекурсия становится подозрительно глубокой - это защищает от худшего случая quicksort.
• Очереди с приоритетом (priority queue) в большинстве стандартных библиотек - те же структуры данных «куча», что использует heapsort, применяются напрямую для планировщиков задач и алгоритмов на графах.