PY
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
def sift_down(unsorted, index, size):
l = 2 * index +1
r = 2 * index +2
largest = index
# comparing a node an its left child
# size have to be minused 1 since we start at index 0
if l <= size-1 and unsorted[l] > unsorted[largest]:
largest = l
# comparing either the siblings or the node and its right child
if r <= size-1 and unsorted[r] > unsorted[largest]:
largest = r
if largest != index:
unsorted[index],unsorted[largest] = unsorted[largest],unsorted[index]
sift_down(unsorted, largest, size)
def sort(unsorted):
size = len(unsorted)
# we divide size by 2(to get to the leftmost part of the tree or heap) then minus 1 becoz we have to get to the almost last layer of the tree ->to work with the sub-tree
for i in range(size//2-1, -1, -1):
sift_down(unsorted, i, size)
# size - 1 as we start at index 0
for i in range(size-2):
unsorted[0], unsorted[-1] = unsorted[-1], unsorted[0]
size -= 1
Enter to Rename, Shift+Enter to Preview
OUTPUT
Run