ЯндексКонтест. Тема контеста: куча (задача D).
Ограничение: должна быть использована самостоятельно написанная куча.
Язык: python. Реализовать структуру данных (предположительно, класс, с использованием 3 функций).
def heapSort(arr):
n = len(arr)
buildHeap(arr, n)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
def buildHeap(arr, n):
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left arr[largest]:
largest = left
if right arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)