【2.5堆结构和堆排序详解】

堆：

heapinsert()方法：

popMax()&heapify()方法：

heapSort()方法

# arr[0...index-1]已经是大根堆了，某个数现在在index位置，往上继续移动
# heapInsert()作用：使arr[0...index]范围都是大根堆
def heapInsert(arr, index):
    # 停止条件：1父比自己大2到0位置
    while arr[((index - 1) >> 1)] < arr[index]:
        arr[index], arr[((index - 1) >> 1)] = arr[((index - 1) >> 1)], arr[index]
        index = (index - 1) >> 1


# -下去-heapify()作用：某个数在index位置，看能否往下沉（大根堆）
# 不断和左右两孩子比较
# 较大孩子如果比父大，则父节点数下沉，较大的孩子上来，周而复始
def heapify(arr, index, heapSize):
    left = index * 2 + 1  # 左孩子下标
    while left < heapSize:  # 下方还有孩子
        # 两个孩子谁的值大，就把下标给largest
        largest =left + 1 if arr[left + 1] > arr[left] and left + 1 < heapSize else left
        # 父与较大孩子比较，谁的值大，把下标给largest
        largest = index if arr[index] > arr[largest] else largest
        if largest == index:
            break
        arr[index], arr[largest] = arr[largest], arr[index]
        index = largest  # 重置while循环，初始化信息：
        left = 2 * index + 1


# -排序-heapSore()作用：堆排序
def heapSore(arr):
    # 长度判断
    if not arr or len(arr) < 2:
        return arr
    # O(N*logN)一个一个加到数组末尾
    for i in range(len(arr)):  # O(N)
        heapInsert(arr, i)  # O(logN)
    # 直接给一个数组进行堆排序
    # for i in range(len(arr)-1,0,-1):
    # heapify(arr,i,len(arr))
    heapSize = len(arr)
    # 将最大值与末尾互换位置，且有效区减一
    heapSize -= 1
    arr[0], arr[heapSize] = arr[heapSize], arr[0]
    while heapSize > 0:
        heapify(arr, 0, heapSize)
        arr[0], arr[heapSize] = arr[heapSize], arr[0]
        heapSize -= 1
    return arr

arr=[1,23,23,2,4,1,4,6,9,4,43,1,6]
print(heapSore(arr))