Motivation

Пирамидальная сортировка (Heap Sort) использует бинарную кучу для многократного поиска наибольшего оставшегося элемента за время O(log n), обеспечивая надежную сортировку O(n log n).

Зачем изучать пирамидальную сортировку?

• Гарантированное O(n log n): в отличие от быстрой сортировки (Quick Sort), у нее нет худшего случая O(n²).
• In-place (на месте): она выполняет сортировку внутри исходного массива и требует всего O(1) дополнительной памяти, в отличие от сортировки слиянием (Merge Sort).
• Интуитивное понимание кучи: она закрепляет понимание того, как куча хранится в массиве и как операция просеивания вниз (sift-down) поддерживает ее свойства.

Если вы уже изучили курс по кучам (Heap) в этой серии, пирамидальная сортировка — это та самая структура данных, примененная в качестве алгоритма сортировки.