Реализуем пирамидальную сортировку на Python | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
C++ Developer. Professional
-5%
Scala-разработчик
-8%
Backend-разработчик на PHP
-9%
Алгоритмы и структуры данных
-9%
Team Lead
-6%
Архитектура и шаблоны проектирования Golang Developer. Professional
-5%
HTML/CSS
-11%
C# ASP.NET Core разработчик
-5%
Kotlin Backend Developer
-8%
iOS Developer. Professional
-8%
Java Developer. Professional Web-разработчик на Python MS SQL Server Developer Android Developer. Basic Разработчик программных роботов (RPA) на базе UiPath и PIX Microservice Architecture Unity Game Developer. Basic Разработчик голосовых ассистентов и чат-ботов React.js Developer Node.js Developer Интенсив «Оптимизация в Java» Супер-практикум по использованию и настройке GIT Symfony Framework Java Developer. Basic Unity Game Developer. Professional Супер-интенсив Azure
Инфраструктура
Инфраструктурная платформа на основе Kubernetes
-6%
Экспресс-курс «IaC Ansible»
-10%
Administrator Linux.Basic
-10%
Мониторинг и логирование: Zabbix, Prometheus, ELK
-10%
Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes»
-30%
Administrator Linux. Professional
-6%
Экcпресс-курс «ELK»
-10%
Экспресс-курс по управлению миграциями (DBVC)
-10%
Базы данных Network engineer Cloud Solution Architecture Highload Architect Разработчик голосовых ассистентов и чат-ботов VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив "Tarantool"
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Реализуем пирамидальную сортировку на Python

Algo_Deep_9.10-5020-e9da33.png

Пирамидальную сортировку также называют «сортировка кучей». Это довольно популярный алгоритм, сегментирующий список на 2 части: отсортированную и, соответственно, неотсортированную. Давайте посмотрим, как его реализовать на Python.

Пояснение алгоритма

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

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

Для реализации создадим вспомогательную функцию heapify():

def heapify(nums, heap_size, root_index):  
    # Индекс наибольшего элемента считается корневым индексом
    largest = root_index
    left_child = (2 * root_index) + 1
    right_child = (2 * root_index) + 2

    # Если левый потомок корня — это допустимый индекс, а элемент больше,
    # чем текущий наибольший, то мы обновляем наибольший элемент
    if left_child < heap_size and nums[left_child] > nums[largest]:
        largest = left_child

    # То же самое и для правого потомка корня
    if right_child < heap_size and nums[right_child] > nums[largest]:
        largest = right_child

    # Если наибольший элемент уже не корневой, они меняются местами
    if largest != root_index:
        nums[root_index], nums[largest] = nums[largest], nums[root_index]
              heapify(nums, heap_size, largest)

def heap_sort(nums):  
    n = len(nums)

    # Создаём Max Heap из списка
    # 2-й аргумент означает остановку алгоритма перед элементом -1, то есть
    # перед первым элементом списка
    # 3-й аргумент означает повторный проход по списку в обратном направлении, 
    # уменьшая счётчик i на 1 
    for i in range(n, -1, -1):
        heapify(nums, n, i)

    # Перемещаем корень Max Heap в самый конец списка
    for i in range(n - 1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, i, 0)

# Проверяем, что всё работает
random_list_of_nums = [35, 12, 43, 8, 51]  
heap_sort(random_list_of_nums)  
print(random_list_of_nums)

Как правило, время сортировки кучей составляет O(n log n), что быстрее, если сравнивать с сортировкой вставками, сортировкой выборкой и пузырьковой сортировкой (там время сортировки составляет O(n²)).

Источник

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться