algorithm-pattern-python/basic_algorithm/heapsort.py at master · dashidhy/algorithm-pattern-python · GitHub

39 lines (29 loc) · 842 Bytes

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))

Expand file tree