我跟着clrs的书去找algo。 我在试着用python做heapsort。但它给了我一个错误,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)
在大多数编程语言中,数组的大小大于最后一个索引。例如,下面的数组:
A = [1, 2, 3]
,它的大小是3,但是最后一个元素的索引是2(A[3]
应该返回它超出了索引)。您正在验证r是否小于或等于数组大小,因此当r等于时,它比上一个索引大。您的验证应该是:if r < size_of_array
相关问题 更多 >
编程相关推荐