用Python构建MINHEAP

Question

我必须用Python构建一个完整的最小堆实现，而不使用内置堆函数。在

所以我有了parent、left-child和right-child的定义，它们考虑了0中的python number list元素：

from random import randint
import math 

def parent(i):
    x = int(l.index(l[i])) #########3
    y = int(math.floor(x/2))
    return y-1  

def lchild(i):
    x = int(l.index(l[i]))
    y = int(math.floor(x*2))
    return y-1

def rchild(i):
    x = int(l.index(l[i]))
    y = int(math.floor(x*2 + 1))
    return y-1

然后我有一部分代码为我生成（伪）随机列表到listl：

^{pr2}$

在这之前一切都很好。然后我有一个函数bkop，它将表l变成一个最小堆。在

def bkop(l):
        j = 0
        for i in range(0, len(l)):
                if int(l[i]) < int(parent(l[i])): #########2
                        l[i], l[parent(i)] = l[parent(i)], l[i]
                        j = j+1
                if j != 0:
                        bkop(l)

然后我想运行一个程序并查看结果：

bkop(l) #########1
print l

程序崩溃，并出现错误列表索引超出范围指向我标记的3行。我大约一个月前就开始写这篇文章了，我很确定，那个家长，lchild和rchild当时都在工作。你知道吗，怎么了？在

编辑1： 好的，我已经修复了parent/lchild/rchild定义。我检查过了，它们返回正确的值。代码如下：

def parent(i):
    x = i + 1
    y = x//2
    return y-1

def lchild(i):
    x = i + 1
    y = x*2
    return y-1

def rchild(i):
    x = i + 1
    y = x*2 + 1
    return y-1

生成随机列表的函数几乎完好无损。然后我有一个bkop函数（从l列表中生成一个最小堆）。我故意使用前后打印，看看它是否有效。。。但它没有。它两次都返回相同的列表，没有编译错误或其他任何错误。你知道怎么修吗？在

print(l)
def bkop(l): 
        j = 0
        for i in range(0, len(l)):
                if l[i] < parent(i):
                        l[i], l[parent(i)] = l[parent(i)], l[i]
                        j = j+1
                if j != 0:
                        bkop(l)
bkop(l)
print l

编辑2： 好的，我已经按照您的建议修复了bkop：

print bkop(l)
def bkop(l):
        j = 0
        for i in range(1, len(l)):
                if l[i] < l[parent(i)]:
                        l[i], l[parent(i)] = l[parent(i)], l[i]
                        j = j+1
                if j != 0:
                        bkop(l)
bkop(l)
print bkop(l)

但当我运行它时，我首先得到一个随机生成的表（我应该这样做），而不是最小堆表，而是得到None值，如下所示：

[34, 9, 94, 69, 77, 33, 56]
None

有什么想法吗？也许我应该换一种方式来做，不是把l[I]比作父母，而是把l[I]比作左右两个孩子？在

Answer 1

首先：您的parent、lchild和rchild函数有问题：

• l[index]获取给定索引的值。

• l.index(...)获取给定值的索引。

您正在尝试获取特定索引处某个值的索引。就像x + 1 - 1。如果您的项是唯一的，则计算的索引将始终与您开始使用的索引相同。如果存在重复项，则函数将计算该索引处第一次出现的值的父项、左子项和右子项。 这可能不是你想要的。所以将x设置为i，或者完全删除{}。在

实际问题如下：

您的parent、lchild和rchild函数被设计用于index，但是您将索引i处的l的值传递给函数：parent(l[i])

由于列表中的值可能远高于可能的索引范围，因此列表索引超出范围。你可能想直接传递索引。在

此外：

parent、lchild和rchild返回不正确的值。在没有其他东西的情况下测试这些功能！在

我想结果应该是这样的：

• parent(1) == parent(2) == 0
• lchild(0) == 1
• rchild(0) == 2

您的定义返回不同的值。在

一些小事：

• 所有这些随机的int转换都是无用的。将int转换为int没有任何作用。唯一需要转换的行是：``dl=int（input）`
• int(math.floor(x/2))。改用整数除法x // 2
• int(math.floor(x*2))。整数乘以2是整数。不需要floor它。在

编辑 你的bkop函数有两个错误。在

• l[i] < parent(i)将该值与索引进行比较。我想您应该将i处的值与其父值对应，而不是父索引。在
• 对于i == 0，将索引0处的值与parent(0) == -1处的值进行比较。这是围绕在列表中的，可能不是您想要的。由于索引0没有父项，因此不应尝试将其与其父项进行比较。在

编辑2

bkop不返回列表，而是在的位置修改列表。只在结尾print(l)。您将看到原始列表已被修改。在

Answer 2

所以在Wombatz的帮助下，我已经完成了全部工作（非常感谢！）。以下是供未来用户使用的工作代码：

from random import randint

def parent(i):
    x = i + 1
    y = x//2
    return y-1

def lchild(i):
    x = i + 1
    y = x*2
    return y-1

def rchild(i):
    x = i + 1
    y = x*2 + 1
    return y-1



l = []
dl = int(input())

for i in range (0, dl):
    x = int(randint(1,100)) 
    l.append(x) 

print l
def bkop(l):
        j = 0
        for i in range(1, len(l)):
                if l[i] < l[parent(i)]:
                        l[i], l[parent(i)] = l[parent(i)], l[i]
                        j = j+1
                if j != 0:
                        bkop(l)
bkop(l)
print l

运行时，我在列表长度的输入中输入了13，得到了结果：

^{pr2}$