使用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))

我将输出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]