一、堆：是一種資料結構，一種叫做完全二叉樹的資料結構，
二、堆的性質：
1、大頂堆：每個節點的值都大于或者等于它的左右子節點的值，
大頂堆性質：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]
2、小頂堆：每個節點的值都小于或者等于它的左右子節點的值，
小頂堆性質：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]
3、堆排序的基本思想：
（1）將帶排序的序列構造成一個大頂堆，根據大頂堆的性質，當前堆的根節點（堆頂）就是序列中最大的元素；
（2）將堆頂元素和最后一個元素交換，然后將剩下的節點重新構造成一個大頂堆；
（3）重復步驟2，如此反復；
（4）從第一次構建大頂堆開始，每一次構建，我們都能獲得一個序列的最大值，然后把它放到大頂堆的尾部，
（5）最后，就得到一個有序的序列了，
4、非葉子節點的確認：
（1）根據大頂堆的性質，每個節點的值都大于或者等于它的左右子節點的值，
所以我們需要找到所有包含子節點的節點，也就是非葉子節點，然后調整他們的父子關系，
非葉子節點遍歷的順序應該是從下往上，這比從上往下的順序遍歷次數少很多，
因為，大頂堆的性質要求父節點的值要大于或者等于子節點的值，
如果從上往下遍歷，當某個節點即是父節點又是子節點并且它的子節點仍然有子節點的時候，
因為子節點還沒有遍歷到，所以子節點不符合大頂堆性質，當子節點調整后，必然會影響其父節點需要二次調整，
但是從下往上的方式不需要考慮父節點，因為當前節點調整完之后，當前節點必然比它的所有子節點都大，
所以，只會影響到子節點二次調整，
相比之下，從下往上的遍歷方式比從上往下的方式少了父節點的二次調整，
（2）如何知道最后一個非葉子節點的位置，也就是索引值？
對于一個完全二叉樹，在填滿的情況下（非葉子節點都有兩個子節點），
每一層的元素個數是上一層的二倍，
根節點數量是1，所以最后一層的節點數量，一定是之前所有層節點總數+1，
所以，我們能找到最后一層的第一個節點的索引，即節點總數/2（根節點索引為0），
這也就是第一個葉子節點，所以第一個非葉子節點的索引就是第一個葉子結點的索引-1，
那么對于填不滿的二叉樹呢？這個計算方式仍然適用，當我們從上往下，從左往右填充二叉樹的程序中，
第一個葉子節點，一定是序列長度/2，所以第一個非葉子節點的索引就是arr.length / 2 -1，
三、參考原地址：https://blog.csdn.net/qq_28063811/article/details/93034625
四、Python排序：
#堆排序
#構建大頂堆
def heapify(arr,n,i):
largest=i # 索引 i 作為比較的節點索引位置
l=2*i+1 #left=2*i+1
r=2*i+2 #right=2i+1
#由左到右：節點值與下級左右節點值比較
#節點 i 小于子左節點值，再用子左節點值與右節點值比較
if l<n and arr[i]<arr[l]: #">"由大到小排序；"<"有小到大排序
largest=l #如果子左節點值大，則用子左節點值與子右節點值比較
if r<n and arr[largest]<arr[r]: #">"由大到小排序；"<"有小到大排序
largest=r #
if largest !=i: #如果發現 i 節點值比左右子節點值小，則把做大的子節點值與 i 位置的值交換，實作大頂堆的性質，
arr[i],arr[largest]=arr[largest],arr[i] #交換
heapify(arr,n,largest) #然后 遞回此程序
def heapSort(arr):
n=len(arr)
#建 大頂堆
#從下往上構建大頂堆
for i in range(n,-1,-1): # i 從取最大位置索引開始
heapify(arr,n,i)
#一個個交換元素
#大頂堆構建完成后，跟節點值與最后節點值交換,最大值放到了串列的最后
#然后再從根節點索引位置開始，再次進行大頂堆的構建
#再把跟節點值與 i 索引的值交換，依次遞回
for i in range(n-1,0,-1): # i ：數列元素的個數逐漸減少
arr[i],arr[0]=arr[0],arr[i] #交換
heapify(arr,i,0) #從根節點開始從已構建的大頂堆再次重構
#測驗
arr=[4,5,8,2,3,9,7,1]
heapSort(arr)
n=len(arr)
print("排序后")
for i in range(n):
print("%d" %arr[i])
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/338908.html
標籤：Python