堆排序：這里用數(shù)組arr表示堆的結(jié)構(gòu)(完全二叉數(shù)颁褂，且root.val大于等于孩子結(jié)點(diǎn))趾牧，即arr[0]代表樹(shù)的根結(jié)點(diǎn)检盼，arr[1]代表root.left;arr[2]代表root.right;
arr[3] = root.left.left ; arr[4] = root.left.right; arr[5] = root.right.left;.....
class HeapSort:
def heapAdjust(self, arr, n ,i):
largest = i #當(dāng)前結(jié)點(diǎn)index（在arr數(shù)組中）
left = 2*i+1 #當(dāng)前結(jié)點(diǎn)left index
right = 2*i+2 #當(dāng)前結(jié)點(diǎn)right index
if left<n and arr[left]>arr[largest]:
largest = left
if right<n and arr[right]>arr[largest]:
largest = right
if largest!=i:
arr[i],arr[largest]=arr[largest],arr[i]
self.heapAdjust(arr,n,largest)
def heapSort(self,arr):
#步驟(1)：建立堆
#自底向上調(diào)整使得根結(jié)點(diǎn)大于等于其孩子結(jié)點(diǎn)，最后調(diào)整的是index=0的根結(jié)點(diǎn)翘单；
#int(len(arr)/2)-1保證為非葉子結(jié)點(diǎn)吨枉，先在底部的根結(jié)點(diǎn)處調(diào)整，然后逐步向上到root根結(jié)點(diǎn)
n = len(arr)
for i in range(int(n/2-1),-1,-1):
self.heapAdjust(arr,n,i)
# 步驟(2)：把root作為最大數(shù)組放在數(shù)組后面哄芜，然后調(diào)整數(shù)組為arr[n-1]的堆
#arr[0],arr[i]=arr[i],arr[0]即把堆中最后一個(gè)放在堆頂貌亭，然后下沉調(diào)整。
for i in range(n-1,-1,-1):
arr[0],arr[i]=arr[i],arr[0]
self.heapAdjust(arr,i,0)
if __name__=="__main__":
so = HeapSort()
arr = [1,3,6,5,9,8]
res = so.heapSort(arr)
print(arr)
參考
https://zhuanlan.zhihu.com/p/52884590
https://zhuanlan.zhihu.com/p/34324469
