使用python构建最大堆时遇到错误的输出结果

Question

我试图在python中建立最大的堆，我已经做了，但在heapify后的列表输出不满足最大堆属性。任何一个人可以帮助解决这个问题

def max_heapify(arr,i):
    left = 2 *i 
    right = 2 * i + 1
    length = len(arr)-1
    largest = i
    if length > left and arr[largest] < arr[left]:
        largest = left
    if length > right and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        arr[largest],arr[i] = arr[i],arr[largest]
        max_heapify(arr,largest)
def build_max_heap(arr):
    for i in reversed(range(len(arr)//2)):
        max_heapify(arr,i)
    return arr

arr = [1,12,9,5,6,10]
print(build_max_heap(arr))

我得到了不满足最大堆属性的out put [12, 9, 6, 5, 1, 10]。

Answer 1

有两个问题。

• 首先，堆是基于0的(根在索引0处)，所以节点0的子节点将是1和2，因此节点i的子节点将是2*i+1和2*i+2。
• 您的代码在交换前比较了两个子代，但没有将较大的子代与父代进行比较，只有当子代比父代大时才应该交换

def max_heapify(arr,i):
    left = 2 *i + 1
    right = 2 * i + 2
    length = len(arr)
    largest = i
    if length > left and arr[largest] < arr[left]:
        largest = left
    if length > right and arr[largest] < arr[right]:
        largest = right
    if arr[largest] > arr[i]:
        arr[largest], arr[i] = arr[i],arr[largest]
        max_heapify(arr,largest)

def build_max_heap(arr):
    N = len(arr)
    for i in reversed(range(len(arr)//2)):
        max_heapify(arr,i)
    return arr

arr = [1,12,9,5,6,10]
print(build_max_heap(arr))

arr = [1,12,9,5,6,10,13]
print(build_max_heap(arr))


output:
[12, 6, 10, 5, 1, 9]                                                                                                                                                               
[13, 12, 10, 5, 6, 1, 9]