python - 堆排序算法问题

Question

我遵循了算法的 clrs 书。我正在尝试在 python 中进行堆排序。但它给我的错误是 r 落在索引的一边，但我不知道为什么。

def Max_Heapify(A,i,size_of_array):
    l = 2*i
    r = l + 1
    if l <= size_of_array and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= size_of_array and A[r] > A[largest]:
        largest = r
    if i != largest:
        A[i], A[largest] = A[largest], A[i]
        Max_Heapify(A,largest,size_of_array)

def Build_Max_Heap(A,size_of_array):
    for i in range((math.floor(size_of_array/2)) - 1 , 0 ,-1):
        Max_Heapify(A,i,size_of_array)

def Heapsort(A,size_of_array):
    Build_Max_Heap(A,size_of_array)
    for i in range(size_of_array - 1 ,0 ,-1):
        A[0],A[i] = A[i],A[0]
        size_of_array = size_of_array - 1
        Max_Heapify(A,0,size_of_array)

Answer 1

在大多数编程语言中，数组的大小都大于最后一个索引。例如，以下数组:A = [1, 2, 3] ，它的大小是 3，但最后一个元素的索引是 2(A[3] 应该返回它超出索引)。您正在验证 r 是否小于或等于数组大小，因此当它等于时，它大于最后一个索引。您的验证应该是:

if r < size_of_array