算法學習：堆排序

#調整堆結果
def heapify(arr,action_node_index,length):
    '''
    arr:要傳入的數(shù)組
    action_node_index:待調整的堆的節(jié)點的索引
    length :堆的規(guī)模
    '''
    left_child_index = 2*action_node_index+1
    right_child_index = 2*action_node_index+2
    max_value_index = action_node_index
    #分別和左右子節(jié)點比較，找到最大的值對應的index
    #在查找的堆的范圍內
    if left_child_index<length and arr[left_child_index]>arr[max_value_index]:
        max_value_index = left_child_index
    if right_child_index<length and arr[right_child_index]>arr[max_value_index]:
        max_value_index = right_child_index
    #如果最大值的索引發(fā)生了變化,交換位置
    if max_value_index!=action_node_index:
        arr[max_value_index],arr[action_node_index]=arr[action_node_index],arr[max_value_index]
        #因為位置的交換，可能導致交換后的堆不滿足堆的結構
        #繼續(xù)調整基于該節(jié)點為根的堆結構
        heapify(arr,max_value_index,length)


#建堆：從最后一個非葉子節(jié)點
def buildheapify(arr):
    for i in range(len(arr)//2-1,-1,-1):#左必右開，到0索引結束
        heapify(arr,i,len(arr))

#堆排序
def heapifySort(arr):
    length = len(arr)
    buildheapify(arr)
    for i in range(length):
        #做交換
        arr[0],arr[length-i-1]=arr[length-i-1],arr[0]
        #調整堆
        heapify(arr,0,length-1-i)
    return arr

arr = [-111,12,0,-6,12,88,34,8,-3]
print(heapifySort(arr))
#結果
[-111, -6, -3, 0, 8, 12, 12, 34, 88]