本文實例講述了Python實現(xiàn)堆排序的方法。分享給大家供大家參考，具體如下：
堆排序作是基本排序方法的一種，類似于合并排序而不像插入排序，它的運行時間為O(nlogn)，像插入排序而不像合并排序，它是一種原地排序算法，除了輸入數(shù)組以外只占用常數(shù)個元素空間。
堆（定義）：（二叉）堆數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組對象，可以視為一棵完全二叉樹。如果根結(jié)點的值大于（小于）其它所有結(jié)點，并且它的左右子樹也滿足這樣的性質(zhì)，那么這個堆就是大（小）根堆。
我們假設(shè)某個堆由數(shù)組A表示，A[1]為樹的根，給定某個結(jié)點的下標(biāo)i，其父結(jié)點、左孩子、右孩子的下標(biāo)都可以計算出來：
PARENT(i):
return i/2
LEFT(i):
return 2i
RIGHT(i):
return 2i+1
堆排序Python實現(xiàn)
所謂堆排序的過程，就是把一些無序的對象，逐步建立起一個堆的過程。
下面是用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): """調(diào)整列表中的元素以保證以index為根的堆是一個最大堆""" # 將當(dāng)前結(jié)點與其左右子節(jié)點比較，將較大的結(jié)點與當(dāng)前結(jié)點交換，然后遞歸地調(diào)整子樹 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): """堆排序""" # 先將列表調(diào)整為堆 build_max_heap(to_sort_list) heap_size = len(to_sort_list) # 調(diào)整后列表的第一個元素就是這個列表中最大的元素，將其與最后一個元素交換，然后將剩余的列表再調(diào)整為最大堆 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
