三个月算法进阶--day40

def heap_adjust(L, start, end):
    temp = L[start]
 
    i = start
    j = 2 * i
    while j <= end:
        if j < end and L[j] < L[j + 1]:
            j += 1
        if temp < L[j]:
            L[i] = L[j]
            i = j
            j = 2 * i
        else:
            break
    L[i] = temp

L = collections.deque([50, 15, 7, 80, 2])
L.appendleft(0)
L_length = len(L) - 1
first_sort_count = L_length // 2
for i in range(first_sort_count):
    heap_adjust(L, first_sort_count - i, L_length)

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    # 找到父节点与两个子节点的最大值
    if l < n and arr[i] < arr[l]:
        largest = 1

    if r < n and arr[largest] < arr[r]:
        largest = r
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i] # 下溯

        heapify(arr, n, largest)

arr = [50, 15, 7, 80, 2]
n = len(arr)
for i in range(n, -1, -1):
    heapify(arr, n, i)

for i in range(L_length - 1):
    L[1], L[L_length - i] = L[L_length - i], L[1]
    heap_adjust(L, 1, L_length - i - 1)

for i in range(n-1, 0, -1):
    arr[i], arr[0] = arr[0], arr[i]
    heapify(arr, i, 0)