def heap_adjust(A, start=0, end=None):
if end is None:
end = len(A)
while start is not None and start < end // 2:
l, r = start * 2 + 1, start * 2 + 2
swap = None
if A[l] > A[start]:
swap = l
if r < end and A[r] > A[start] and (swap is None or A[r] > A[l]):
swap = r
if swap is not None:
A[start], A[swap] = A[swap], A[start]
start = swap
return
def heapsort(A):
# construct max heap
n = len(A)
for i in range(n // 2 - 1, -1, -1):
heap_adjust(A, i)
# sort
for i in range(n - 1, 0, -1):
A[0], A[i] = A[i], A[0]
heap_adjust(A, end=i)
return A
# test
if __name__ == '__main__':
a = [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10]
print(a)
print(heapsort(a))