Max Heapify代码.在python中从0开始索引为1？

Question

def max_heapify(arr, n, i):  

    largest = i
    left = 2*i
    right = 2*i + 1
    while left <= n and arr[left] > arr[largest]:
        largest = left

    while right <= n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[largest], arr[i] = arr[i], arr[largest]
        print(arr)   
        max_heapify(arr, n, i)

arr=[9, 6, 5, 0, 8, 2, 7, 1,3]  
n = len(arr)
i = int(n/2)  
max_heapify(arr, n, i)

上面的Max Heapify代码因为从Array 0开始，所以失败了，怎么才能把它改成1呢？

Answer 1

对于一个从0开始的数组，你需要比较以下内容 left < n 和 right < n 此外，你的最初的左和右应该是 left = 2 * i + 1 和 right = 2 * i + 2. 要检索最大堆，你还需要调用 max_heapify 最后，当你确信它只发生一次时，就不需要while循环了。下面是一段工作代码，可以返回你所需要的结果。

def max_heapify(arr, n, i):  

    left = 2*i + 1
    right = 2*i + 2

    if left < n and arr[left] > arr[i]:
        largest = left
    else:
        largest = i

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[largest], arr[i] = arr[i], arr[largest]
        print(arr)   
        max_heapify(arr, n, largest)

if __name__ == "__main__":
    arr=[9, 6, 5, 0, 8, 2, 7, 1,3]  
    n = len(arr)
    i = int((n-1)/2)  
    for b in reversed(range(0,i)):
        max_heapify(arr, n, b)