Сортировка кучей (Heap Sort)

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

▎Основные этапы работы Heap Sort:

1. Построение кучи:

• Сначала необходимо преобразовать массив в кучу. В зависимости от реализации может быть использована максимальная куча (max-heap) или минимальная куча (min-heap). В случае максимальной кучи родительский элемент всегда больше или равен своим дочерним элементам.

• Для построения кучи используется метод "просеивания" (sift down), начиная с последнего узла, который имеет дочерние элементы, и перемещаясь вверх по дереву.

2. Сортировка:

• После того как куча построена, самый большой элемент (корень кучи) будет находиться в начале массива. Этот элемент помещается в конец массива, и размер кучи уменьшается.

• Затем выполняется операция просеивания для восстановления свойств кучи для оставшихся элементов.

• Этот процесс повторяется, пока все элементы не будут отсортированы.

▎Временная сложность:

• Лучший случай: O(n*log(n))

• Средний случай: O(n*log(n))

• Худший случай: O(n*log(n))

▎Пространственная сложность:

• O(1) — Heap Sort выполняется in-place и не требует дополнительной памяти для хранения временных массивов.

▎Устойчивость:

Данный алгоритм сортировки не является устойчивым, это означает, что при сортировке элементов с одинаковыми ключами их относительный порядок не сохраняется. То есть, если два элемента имеют одинаковое значение и один из них идет перед другим в исходном массиве, то после сортировки первый элемент не обязательно останется перед вторым.

Реализация алгоритма на C++:

Реализация алгоритма на Python: