0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: python, алгоритмы для разработчиков, пирамидальная сортировка, max heap, сортировка кучей</p>
1
<p>Теги: python, алгоритмы для разработчиков, пирамидальная сортировка, max heap, сортировка кучей</p>
2
<p>Пирамидальную сортировку также называют "сортировка кучей". Это довольно популярный алгоритм, сегментирующий список на 2 части: отсортированную и, соответственно, неотсортированную. Давайте посмотрим, как его реализовать на Python.</p>
2
<p>Пирамидальную сортировку также называют "сортировка кучей". Это довольно популярный алгоритм, сегментирующий список на 2 части: отсортированную и, соответственно, неотсортированную. Давайте посмотрим, как его реализовать на Python.</p>
3
<h2>Пояснение алгоритма</h2>
3
<h2>Пояснение алгоритма</h2>
4
<p>При реализации пирамидальной сортировки мы сначала выполняем преобразование списка в<strong>Max Heap</strong>- бинарное дерево, в котором наибольший элемент - это вершина дерева. Потом этот элемент помещается в конец списка, после чего Max Heap перестраивается, а новый наибольший элемент помещается перед последним элементом в нашем списке. Процесс построения кучи повторяется до тех пор, пока все вершины дерева не будут удалены.</p>
4
<p>При реализации пирамидальной сортировки мы сначала выполняем преобразование списка в<strong>Max Heap</strong>- бинарное дерево, в котором наибольший элемент - это вершина дерева. Потом этот элемент помещается в конец списка, после чего Max Heap перестраивается, а новый наибольший элемент помещается перед последним элементом в нашем списке. Процесс построения кучи повторяется до тех пор, пока все вершины дерева не будут удалены.</p>
5
<h2>Реализация алгоритма</h2>
5
<h2>Реализация алгоритма</h2>
6
<p>Для реализации создадим вспомогательную функцию heapify():</p>
6
<p>Для реализации создадим вспомогательную функцию heapify():</p>
7
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)<p>Как правило, время сортировки кучей составляет O(n log n), что быстрее, если сравнивать с сортировкой вставками, сортировкой выборкой и пузырьковой сортировкой (там время сортировки составляет O(n²)).</p>
7
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)<p>Как правило, время сортировки кучей составляет O(n log n), что быстрее, если сравнивать с сортировкой вставками, сортировкой выборкой и пузырьковой сортировкой (там время сортировки составляет O(n²)).</p>
8
<p><a>Источник</a></p>
8
<p><a>Источник</a></p>
9
9