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 уже heapified , вы неправильно реализуете метод 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

Надеюсь это помогает.