​​Heap Sort (Сортировка кучей)

Сортировка кучей, пирамидальная сортировка — алгоритм сортировки, использующий структуру данных двоичная куча. Это неустойчивый алгоритм сортировки с временем работы O(nlogn)
, где n
— количество элементов для сортировки, и использующий O(1)
дополнительной памяти.

Реализация на Python
# Программа Python для реализации сортировки кучи
# Чтобы скопировать поддерево с корневым индексом i.
#@python_lounge

# n - размер кучи  
def heapify(arr, n, i):
    largest = i # Инициализировать largest как root
    l = 2 * i + 1    # left = 2*i + 1
    r = 2 * i + 2    # right = 2*i + 2
  
    # Проверить, существует ли левый дочерний элемент root и есть ли
    # больше, чем корень

    if l < n and arr[i] < arr[l]:
        largest = l
  
# Проверить, существует ли правый дочерний элемент root и есть ли он
    # больше, чем корень

    if r < n and arr[largest] < arr[r]:
        largest = r
  
  # Сменить корень, если нужно
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i] # swap
  
        # Заполнить корень.
        heapify(arr, n, largest)
  
# Основная функция для сортировки массива заданного размера
def heapSort(arr):
    n = len(arr)
  
    # Создание maxheap.
    # Поскольку последний родитель будет в ((n // 2) -1), мы можем начать с этого места.

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
  
  # Один за другим извлечь элементы
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)
  
# Код драйвера для тестирования выше
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
    print ("%d" %arr[i]),