Пирамидальная сортировка в Python
Python3 ПримерыПирамидальная сортировка — это алгоритм сортировки, разработанный с использованием структуры данных «куча». Куча — это структура, которая приближенно представляет полное бинарное дерево и при этом удовлетворяет свойству кучи: то есть ключ или индекс дочернего узла всегда меньше (или больше) его родителя. Можно сказать, что пирамидальная сортировка — это сортировка выбором, использующая понятие кучи для сортировки.
Пример
def heapify(arr, n, i):
largest = i
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # Обмен
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Построить максимальную кучу.
for i in range(n, -1, -1):
heapify(arr, n, i)
# Обменять элементы по одному
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Обмен
heapify(arr, i, 0)
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("После сортировки")
for i in range(n):
print ("%d" %arr[i]),
Результат выполнения приведённого выше кода:
排序后 5 6 7 11 12 13Другие расширения