为什么堆排序算法中的build_heap函数不执行

Question

以下用于实现堆排序算法的python代码以及max_heapiy和build_heap函数导致以下错误消息：

Traceback (most recent call last):
File "heap.py", line 30, in <module>
build_heap(arr)
File "heap.py", line 25, in build_heap
for i in range(((int(len(array))-1)/2),0,-1):
TypeError: 'float' object cannot be interpreted as an integer

代码：

def left(i):
return(2*i)
def right(i):
return(2*i+1)
def max_heapify(array,i,heap_size):
l=left(i)
r=right(i)
largest=i
if(l<=heap_size and array[l]>array[i]):
largest=l
elif(r<=heap_size and array[r]>array[i]):
largest=r
if(largest!=i):
swap(array,i,largest)
max_heapify(array,largest)


def swap(array,a,b):
array[a],array[b]=array[b],array[a]
def build_heap(array):
heap_size=len(array)-1
for i in range(((int(len(array))-1)/2),0,-1):
max_heapify(array,i,heap_size)

arr=[0,10,9,8,7,6,5,4,3,2,1,0]
build_heap(arr)
print(arr)

Answer 1

int(len(array) - 1) / 2是一个浮点值，因为您在转换为整数后除以2。只需执行(len(array) - 1) // 2，它将给出一个整数。

您还应该为列表的第一个元素调用max_heapify，因此考虑到这两个更改，您的循环需要是for i in range((len(array)-1)//2, -1, -1)。

(我假设这只是一个拼写错误，但当你从max_heapify内部调用它时，你只向它传递了两个参数，你需要添加heap_size(。

Answer 2

这可能是在python-2.x中编写的。如果在python2.x中对两个整数进行除法运算，则执行整数除法运算。在python-3.x中，您可以使用//(也适用于python-2.x(：

def build_heap(array):
heap_size=len(array)-1
for i in range(heap_size//2, -1, -1):
max_heapify(array,i,heap_size)