#堆排序
def heap_sort(arr):
    root = len(arr)//2-1
    while(root>=0):
        heap_adjust(arr,root,len(arr)-1)    
        root=root-1   # 此時生成的大頂堆，滿足每個根節點為子樹中最大，因此，之后只需要對最頂的子樹進行調整
        
    i = len(arr)-1
    while i>=0:
        arr[0],arr[i] = arr[i],arr[0]
        heap_adjust(arr,0,i-1)
        i=i-1
        
def heap_adjust(arr,start,end):
    temp=arr[start]       # 臨時變量存儲‘頂’位置的數據，temp不發生變化
    son=2*start+1         # son記錄‘頂’的左節點的下標
    while son<=end:      # 循環條件耐琢磨，先往下看
        if son
              
                =arr[son]:       # 第一輪判斷是否為大頂堆，第二輪比較臨時變量和下層的son的值得大小
            break                # 如果是大頂，直接退出while循環
        arr[start]=arr[son]      # 較大的左/右節點的值給‘頂’的位置，注意，此時該節點的值沒有和‘頂’交換
        start=son                # ‘頂’的坐標指向下層的son
        son=2*son+1
    arr[start]=temp             # 將temp存儲的原‘頂’的值，賦給start指向的位置，即最后的son的位置。
              
            
          

heap_adjust()函數的功能是將完全二叉樹中，以start為根節點的子樹進行構造大頂堆， 同時保證該子樹的子樹也是大頂堆。 這句話比較拗口。

舉例：此時start為最頂端，元素為30，且不是最大值，那么在元素30下沉的過程中，會保證30下沉到合適位置，可能進行多次下沉，而不是只進行一次下沉。

heap_sort()函數中，有root = len(arr)//2-1，此位置是樹中最后一個非葉子節點。

函數有兩個循環，第一個循環是從最后一個非葉子節點一直往前作為堆頂。最后將序列構造成大頂堆。

原理是：從下往上，從右往左，將每個非葉子節點當做根節點，將其和其子樹調整成大頂堆。

第二個循環是逐步將每個頂與末尾元素交換，并且再調整成大頂堆。