/
heapsort.py
47 lines (41 loc) · 1.17 KB
/
heapsort.py
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#!/usr/bin/python2
def swap(array, i, j):
tmp = array[i]
array[i] = array[j]
array[j] = tmp
def heapify(array):
""" Build heap """
# Middle in array
start = (len(array) - 2) / 2
while start >= 0:
perc_down(array, start, len(array) - 1)
start -= 1
def perc_down(array, start, end):
""" Check/modify heap structure """
largest = 2 * start + 1
while largest <= end:
# left child < right child
if (largest < end) and (array[largest] < array[largest + 1]):
largest += 1
# biggest child > parent
if (array[largest] > array[start]):
swap(array, largest, start)
start = largest
largest = 2 * start + 1
else:
return
def heap_sort(array):
""" Sorting function """
# biggest to smallest
heapify(array)
end = len(array) - 1
while end > 0:
# swap biggest node with end node
swap(array, end, 0)
# make sure first node is biggest
perc_down(array, 0, end - 1)
end -= 1
if __name__ == "__main__":
array = [17, 9, 13, 8, 7, -5, 6, 11, 3, 4, 1, 2]
heap_sort(array)
print(array)