blob: 53fcb7ed2538468f344ee4ec23598cd3a094fe22 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
def heap_sort(arr):
heapify(arr)
end = len(arr) - 1
while end > 0:
arr[end], arr[0] = arr[0], arr[end]
shift_down(arr, 0, end - 1)
end -= 1
return arr
def heapify(arr):
start = len(arr) // 2
while start >= 0:
shift_down(arr, start, len(arr) - 1)
start -= 1
def shift_down(arr, start, end):
root = start
while root * 2 + 1 <= end:
child = root * 2 + 1
if child + 1 <= end and arr[child] < arr[child + 1]:
child += 1
if child <= end and arr[root] < arr[child]:
arr[root], arr[child] = arr[child], arr[root]
root = child
else:
return
|
