python - 添加新元素时 Heapify 不起作用

Question

我想插入一些节点，看来这个功能有问题。可以插入但不能执行heapify。我想知道添加新元素后索引是否困惑。欢迎任何评论。谢谢。

def heapify(arr, n, i): 
    smallest = i  
    l = 2 * i + 1  
    r = 2 * i + 2  

    if l < n and arr[l] < arr[smallest]:  
        smallest = l  

    if r < n and arr[r] < arr[smallest]:  
        smallest = r  

    if smallest != i:  
        (arr[i],  
         arr[smallest]) = (arr[smallest], 
                           arr[i]) 

        heapify(arr, n, smallest) 

def insertNode(arr, n, key):
    n=n+1
    arr.append(key)
    heapify(arr, n, n-1)

def printArray(arr, n):    
    for i in range(n):
        print(arr[i])


alist = [8, 9, 15, 16, 11, 17]
n = len(alist)
insertNode(alist, n, 12)
insertNode(alist, n, 18)
insertNode(alist, n, 6)
printArray(alist, n+3)

Answer 1

考虑到alist已经堆化，当您插入节点时，您错误地实现了heapify方法在堆中，您必须采取自下而上的方法，我对您的代码做了一些更正，看看它，

def heapify(arr, n, i):
    parent = (i - 1) // 2

    if parent >= 0 and  arr[i] < arr[parent]:
        arr[i], arr[parent] = arr[parent], arr[i]

        heapify(arr, n, parent)

def insertNode(arr, key):
    arr.append(key)
    n = len(arr)
    heapify(arr, n, n-1)


def printArray(arr, n):
    for i in range(n):
        print(arr[i])


alist = [8, 9, 15, 16, 11, 17]
n = len(alist)

insertNode(alist, 12)
insertNode(alist, 18)
insertNode(alist, 6)
n += 3  # ---> increment size of array after inserting element

printArray(alist, n)

输出将为，

6
8
12
9
11
17
15
18
16

希望有帮助。