在Python中构建MIN-HEAP

Question

我必须在Python中构建完整的MIN-HEAP实现，而不使用内置的堆函数。

所以我有父母，左子女和右子女的定义，这需要在考虑从0蟒蛇号码列表元素：

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 

那么我的生成代码（伪）的一部分随机列表我到列表升：

l = [] 
dl = int(input) 

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

与直到此时一切正常良好。然后我有一个函数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工作。你知道吗，怎么了？

EDIT1： 好的，所以我修复了父/子/儿的定义。我检查过，他们返回正确的值。这里是代码：

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函数（这使得列表中的最小堆不在列表中）。我在目的之前和之后使用打印，以确定它是否有效......但事实并非如此。它两次返回相同的列表，没有编译错误或任何东西。任何想法如何解决它？

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 

EDIT2： 好了，我已经固定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) 

但是当我运行它，我得到这个第一个随机生成的表格（如我应该），和而不是最小堆表，我得到无值，如下图所示：

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

任何IDE如？也许我应该以另一种方式去做，而不是将l [i]与父母进行比较，但是l [i]是左右儿童？

Answer 1

所以我已经得到了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输入列表长度和我已经得到了结果：

13 
[30, 62, 9, 100, 75, 73, 57, 82, 2, 76, 2, 50, 41] #before heapify 
[2, 2, 30, 62, 9, 41, 57, 100, 82, 76, 75, 73, 50] #after heapify 

Answer 2

起初：有一个问题，您parent，lchild和rchild功能：

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

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

您正试图获取特定索引值的索引。这就像x + 1 - 1。如果您的项目是唯一的，那么计算出的索引将始终与您开始使用的索引相同。当有重复时，你的函数将计算该索引值第一次出现的父，左和右子。 这可能不是你想要的。因此请将x设置为i或完全删除x。

实际问题如下：

你parent，lchild和rchild功能desined到上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没有父母，因此您不应该尝试将其与父母进行比较。

EDIT2

bkop不会返回列表中，但修改它就地。最后只需print(l)。您会看到原始列表已被修改。