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

Question

我的作业这道题通过了一个列表，其中索引1是新节点，也是根节点。然后我必须检查它的 children 是否比它本身小，并将它与较小的 child 交换。我写了一些代码，但它不起作用。

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

修改了那些 children 不存在的索引的算法。
For : values = [0, 100, 7, 11, 9, 8, 45, 12, 16, 27, 36] for 100 在 2 次交换后索引 5 没有正确的 child 所以当它超过列表的长度时我们只是将它设置回原始索引。
堆化列表：Binary heap = [0, 7, 8, 11, 9, 36, 45, 12, 16, 27, 100].

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

How to swap the new added number into the correct position in binary heap?

python

python-3.x

heap

min-heap