1 #!/usr/bin/env python
 2 
 3 def heap_sort(elems):
 4     def siftdown(elems, e, begin, end):
 5         i, j = begin, begin*2+1
 6         while j < end:
 7             if j+1 < end and elems[j+1] < elems[j]:
 8                 j += 1
 9             if e < elems[j]:
10                 break
11             elems[i] = elems[j]
12             i, j = j, 2*j + 1
13         elems[i] = e
14 
15     end = len(elems)
16     for i in range(end//2, -1, -1):
17         siftdown(elems, elems[i], i, end)
18     for i in range((end-1), 0, -1):
19         e = elems[i]
20         elems[i] = elems[0]
21         siftdown(elems, e, 0, i)
22 
23 if __name__ == "__main__":
24     l = [5,3,9,6,2,7,1,4,8]
25     heap_sort(l)
26     print(l)