最大堆插入函数python

Question

我为最大堆写了这个插入函数：

def insertinmaxheap(arryhp, num):
    arryhp.append(num)
    arryhp.insert(0, 0)
    l = len(arryhp) - 1
    b = True
    while b:
        print(arryhp)
        print(l)
        print(int(l/2))
        if num <= arryhp[int(l / 2)] or int(l/2) < 2:
            b = False
        arryhp[l] = arryhp[int(l/2)]
        arryhp[int(l/2)] = num
        l = int(l/2)
    return arryhp[1:len(arryhp)]

我已经用一些值对其进行了测试，大部分时间它都能正常工作，但对于这个例子它失败了：

 insertinmaxheap([50, 30, 20, 15, 10, 8, 16], 19)

输出为 [50, 19, 20, 30, 10, 8, 16, 15]，如您所见，19 不应该存在。

这段代码有什么问题？

Answer 1

有两个问题：

在 b 被设置为 False 之后，交换仍然在退出循环之前执行。执行应该使用 break 跳出循环。这也使得布尔值 b 变得不必要。
条件 int(l/2) < 2 应该是 int(l/2) < 1，因为实际上索引 1 的父级应该 与

其他备注：

使用整数除法运算符代替浮点除法。
切片到最后时，使用1:len(arryhp)，可以省略冒号后的部分：1:.
返回的列表不是作为参数给出的变异列表，这不是很好。不应更改输入列表，或者返回的列表是更改后的输入列表。后者可以通过使用 .pop(0).
从列表中弹出第一个值来完成

下面是修改后的代码：

def insertinmaxheap(arryhp, num):
    arryhp.append(num)
    arryhp.insert(0, 0)
    l = len(arryhp) - 1
    while True:
        if num <= arryhp[l // 2] or l // 2 < 1:
            break
        arryhp[l] = arryhp[l//2]
        arryhp[l // 2] = num
        l = l // 2
    arryhp.pop(0)
    return arryhp

现在，这效率不高。该虚拟值的插入和弹出正在消除该算法的时间复杂度。您最好不要插入该虚拟值并使用适当的表达式来确定 parent/child 关系。

此外，您不必在循环的[=43=]每次迭代中将num 分配给堆中的新插槽。在循环结束并确定 num 的最终目的地后，执行一次就足够了：

def insertinmaxheap(arryhp, num):
    arryhp.append(num)
    l = len(arryhp) - 1
    while l > 0:
        parent = (l - 1) // 2
        if num <= arryhp[parent]:
            break
        arryhp[l] = arryhp[parent]
        l = parent
    arryhp[l] = num
    return arryhp

最大堆插入函数python

Max Heap insert function python

algorithm

heap

function

data-structures

python-3.x