Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS.
Пирамидальную сортировку также называют «сортировка кучей». Это довольно популярный алгоритм, сегментирующий список на 2 части: отсортированную и, соответственно, неотсортированную. Давайте посмотрим, как его реализовать на Python.
Пояснение алгоритма
При реализации пирамидальной сортировки мы сначала выполняем преобразование списка в Max Heap — бинарное дерево, в котором наибольший элемент — это вершина дерева. Потом этот элемент помещается в конец списка, после чего Max Heap перестраивается, а новый наибольший элемент помещается перед последним элементом в нашем списке. Процесс построения кучи повторяется до тех пор, пока все вершины дерева не будут удалены.
Реализация алгоритма
Для реализации создадим вспомогательную функцию heapify():
Как правило, время сортировки кучей составляет O(n log n), что быстрее, если сравнивать с сортировкой вставками, сортировкой выборкой и пузырьковой сортировкой (там время сортировки составляет O(n²)).
22 октября в 20:00 пройдёт День открытых дверей курса «Алгоритмы для разработчиков»
День Открытых Дверей — отличная возможность задать преподавателю Никите Овчинникову ( технический руководитель по разработке софта в Skywind Group) все вопросы по курсу, узнать подробнее о программе, особенностях онлайн-формата, навыках, компетенциях и перспективах, которые ждут выпускников после обучения.
Если есть вопрос, запишитесь на онлайн-трансляцию и задайте его в прямом эфире!
ЗАПИСАТЬСЯ НА ДОД