堆排序

堆排序：这里用数组arr表示堆的结构(完全二叉数，且root.val大于等于孩子结点)，即arr[0]代表树的根结点，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 #当前结点index（在arr数组中）
        left = 2*i+1 #当前结点left index
        right = 2*i+2 #当前结点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)：建立堆
        #自底向上调整使得根结点大于等于其孩子结点，最后调整的是index=0的根结点；
        #int(len(arr)/2)-1保证为非叶子结点，先在底部的根结点处调整，然后逐步向上到root根结点
        n = len(arr)
        for i in range(int(n/2-1),-1,-1):
            self.heapAdjust(arr,n,i)
        # 步骤(2)：把root作为最大数组放在数组后面，然后调整数组为arr[n-1]的堆
        #arr[0],arr[i]=arr[i],arr[0]即把堆中最后一个放在堆顶，然后下沉调整。
        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