Почему функция build_heap в алгоритме сортировки кучи не выполняется

Question

Следующий python код для реализации алгоритма сортировки кучи и функций max_heapify и 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 для первого элемента списка - так что, учитывая оба эти изменения, ваш l oop должен быть for i in range((len(array)-1)//2, -1, -1).

(я предполагаю, что это просто опечатка, но вы передаете max_heapify только два аргумента, когда вызываете его изнутри, вам нужно добавить heap_size).

Answer 2

Вероятно, это было написано в python -2.x . Если вы разделите два целых числа в python -2.x , то вы выполните целочисленное деление. В python -3.x вы можете использовать // (что также подходит для python -2.x ):

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