Python堆排序

 1 # -*- coding: utf-8 -*-
 2 
 3 #程序作用：实现最大堆排序
 4 import sys
 5 def left_child(node):
 6     return node*2+1
 7 def right_child(node):
 8     return node*2+2
 9 def max_heapify(array, i, heap_size): 
10     l = left_child(i) 
11     r = right_child(i) 
12  
13     largest = i 
14     if l < heap_size and array[l] > array[i]: 
15         largest = l 
16  
17     if r < heap_size and array[r] > array[largest]: 
18         largest = r 
19  
20     if largest != i: 
21         array[i], array[largest] = array[largest], array[i] 
22         max_heapify(array, largest, heap_size) 
23  
24 def build_max_heap(array):  #建立最大堆
25     for i in range(len(array) / 2, -1, -1): 
26         max_heapify(array, i, len(array)) 
27  
28 def heap_sort(array):       #
29     build_max_heap(array) 
30     for i in range(len(array) - 1, 0, -1): 
31         array[0], array[i] = array[i], array[0] 
32         max_heapify(array, 0, i) 
33  
34 if __name__ == "__main__": 
35     array = [0, 2, 6, 98, 34, 5, 23, 11, 89, 100, 7] 
36     heap_sort(array) 
37  
38     for a in array: 
39         sys.stdout.write("%d " % a)
40  
41