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

HeapSort строит в массиве max-кучу за `O(n)`, а затем `n` раз переносит максимум в конец и восстанавливает кучу за `O(log n)` — итого `O(n log n)` в худшем случае и `O(1)` дополнительной памяти.

Алгоритм

1. Heapify: siftDown для узлов с n/2 − 1 до 0. Дети узла i — 2i + 1 и 2i + 2.
2. Меняем a[0] с последним элементом неотсортированной части, уменьшаем размер кучи, делаем siftDown(0).

Плюсы и минусы

• Гарантированные O(n log n) без буфера и без рекурсии.
• Нестабильна.
• Heapify — O(n), а не O(n log n): большинство узлов внизу и опускаются на пару уровней.
• Плохая локальность: прыжки i → 2i промахиваются мимо кеша, поэтому на практике заметно медленнее QuickSort.

Где уместна

• Как страховка в introsort (std::sort): при глубине рекурсии больше ~2·log n переключаются на heapsort.
• Встраиваемые и real-time системы, где нужен предсказуемый худший случай без аллокаций.
• Частичная сортировка top-k: std::partial_sort построен на куче и работает за O(n log k).

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

HeapSort превращает массив в кучу и раз за разом переносит максимум в конец, гарантируя O(n log n) без дополнительной памяти. На практике она медленнее QuickSort из-за плохой локальности, поэтому ценна как страховка в introsort и там, где важен предсказуемый худший случай.