堆排序作是基本排序方法的一種渊季，類似于合并排序而不像插入排序栖榨，它的運行時間為O(nlogn)靡挥，像插入排序而不像合并排序，它是一種原地排序算法蜈抓，除了輸入數(shù)組以外只占用常數(shù)個元素空間启绰。
堆（定義）：（二叉）堆數(shù)據(jù)結構是一個數(shù)組對象，可以視為一棵完全二叉樹资昧。如果根結點的值大于（小于）其它所有結點酬土，并且它的左右子樹也滿足這樣的性質，那么這個堆就是大（懈翊）根堆。
我們假設某個堆由數(shù)組A表示刹枉，A[1]為樹的根叽唱，給定某個結點的下標i，其父結點微宝、左孩子棺亭、右孩子的下標都可以計算出來：PARENT(i):
return i/2
LEFT(i):
return 2i
RIGHT(i):
return 2i+1
所謂堆排序的過程，就是把一些無序的對象蟋软，逐步建立起一個堆的過程镶摘。
下面是用Python實現(xiàn)的堆排序的代碼。
def build_max_heap(to_build_list):
"""建立一個堆"""
# 自底向上建堆
for i in range(len(to_build_list)/2 - 1, -1, -1):
max_heap(to_build_list, len(to_build_list), i)
def max_heap(to_adjust_list, heap_size, index):
"""調整列表中的元素以保證以index為根的堆是一個最大堆"""
# 將當前結點與其左右子節(jié)點比較岳守，將較大的結點與當前結點交換凄敢，然后遞歸地調整子樹
left_child = 2 * index + 1
right_child = left_child + 1
if left_child < heap_size and to_adjust_list[left_child] > to_adjust_list[index]:
largest = left_child
else:
largest = index
if right_child < heap_size and to_adjust_list[right_child] > to_adjust_list[largest]:
largest = right_child
if largest != index:
to_adjust_list[index], to_adjust_list[largest] = \
to_adjust_list[largest], to_adjust_list[index]
max_heap(to_adjust_list, heap_size, largest)
def heap_sort(to_sort_list):
"""堆排序"""
# 先將列表調整為堆
build_max_heap(to_sort_list)
heap_size = len(to_sort_list)
# 調整后列表的第一個元素就是這個列表中最大的元素，將其與最后一個元素交換湿痢，然后將剩余的列表再調整為最大堆
for i in range(len(to_sort_list) - 1, 0, -1):
to_sort_list[i], to_sort_list[0] = to_sort_list[0], to_sort_list[i]
heap_size -= 1
max_heap(to_sort_list, heap_size, 0)
if __name__ == '__main__':
to_sort_list = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
heap_sort(to_sort_list)
print to_sort_list
