如何将新添加的数字交换到二进制堆中的正确位置？

Question

我作业中的这个问题已经通过了一个列表，其中索引1是新节点，也是根节点。然后我要检查它的孩子是否比它自己小，然后把它和更小的孩子交换。我写了一些代码，但不起作用。你知道吗

def perc_down(data):
    count = 0
    index = 1
    l, r = 2 * index, 2 * index + 1
    while index < len(data):
        if data[index] > data[l] and data[index] > data[r]:
            min_i = data.index(min(data[l], data[r]))
            data[index], data[min_i] = data[min_i], data[index]
            count += 1
            index = min_i
    return count

values = [0, 100, 7, 8, 9, 22, 45, 12, 16, 27, 36]
swaps = perc_down(values)
print('Binary heap =',values)# should be [0, 7, 9, 8, 16, 22, 45, 12, 100, 27, 36]
print('Swaps =', swaps)# should be 3

Answer 1

在while循环中给出l和r值

while index <= len(data) // 2:
    l, r = 2 * index, 2 * index + 1
    if r >= len(data):
        r = index
    if data[index] > data[l] or data[index] > data[r]:
        min_i = data.index(min(data[l], data[r]))
        data[index], data[min_i] = data[min_i], data[index]
        count += 1
        index = min_i
    print(data) #Added this for easy debugging. 
return count

运行循环直到半个值，因为它是二进制最小堆。
输出：

[0, 7, 100, 8, 9, 22, 45, 12, 16, 27, 36]
[0, 7, 9, 8, 100, 22, 45, 12, 16, 27, 36]
[0, 7, 9, 8, 16, 22, 45, 12, 100, 27, 36]
Binary heap = [0, 7, 9, 8, 16, 22, 45, 12, 100, 27, 36]
Swaps = 3

修改了子级不存在的索引的算法。
For:values = [0, 100, 7, 11, 9, 8, 45, 12, 16, 27, 36]For 100在2次交换之后，索引5没有正确的子级，因此当它超过列表长度时，我们只将其设置回原始索引。
堆化列表：Binary heap = [0, 7, 8, 11, 9, 36, 45, 12, 16, 27, 100]。你知道吗