Heap Sort (сортировка кучей) — это алгоритм сортировки, основанный на структуре данных, называемой "куча" (heap). Он использует свойства двоичного дерева для сортировки массивов. ▎Основные этапы работы Heap Sort: 1. Построение кучи: • Сначала необходимо преобразовать массив в кучу. В зависимости от реализации может быть использована максимальная куча (max-heap) или минимальная куча (min-heap). В случае максимальной кучи родительский элемент всегда больше или равен своим дочерним элементам. • Для построения кучи используется метод "просеивания" (sift down), начиная с последнего узла, который имеет дочерние элементы, и перемещаясь вверх по дереву...

Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS. Пирамидальную сортировку также называют «сортировка кучей». Это довольно популярный алгоритм, сегментирующий список на 2 части: отсортированную и, соответственно, неотсортированную. Давайте посмотрим, как его реализовать на Python. Пояснение алгоритма При реализации пирамидальной сортировки мы сначала выполняем преобразование списка в Max Heap — бинарное дерево, в котором наибольший элемент — это вершина дерева...