Термин «кучная сортировка» относится к алгоритму сортировки, который использует структуру данных двоичной кучи для сортировки элементов массива. Он был изобретен Дж. У. Дж. Уильямсом в 1964 году. Название «куча» в кучечной сортировке относится к структуре данных кучи, которая используется в процессе сортировки.

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

Вот пример алгоритма сортировки кучей, реализованного в Python:

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[i] < arr[left]:
        largest = left
    if right < n and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    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]
        heapify(arr, i, 0)
    return arr
# Example usage:
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)

Этот код реализует функцию heapify, которая используется для поддержки свойства кучи, и функцию heap_sort, которая выполняет фактическую сортировку, многократно извлекая максимальный элемент из кучи.