在 Python 建造 MIN-HEAP

Question

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

所以我得到了 parent、左 child 和右 child 的定义，其中考虑了来自 0:[=] 的 python 数字列表元素20=]

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:

l = []
dl = int(input)

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

直到此时一切正常。然后我有一个函数 bkop 用于将 table l 变成 min-heap.

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

程序崩溃并出现错误 list index out of range 指向 3 行，我用 ######### 标记。我大约一个月前开始写这篇文章，我很确定 parent、lchild 和 rchild 当时有效。你知道吗，怎么了？

编辑1：好的，所以我已经修复了 parent/lchild/rchild 定义。我检查过，它们 return 正确的值。这是代码：

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 列表中生成 min-heap）。我故意在前后使用 print 来确定它是否有效......但它没有。它 return 两次都是相同的列表，没有编译错误或任何东西。知道如何解决吗？

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)

但是当我运行它时，我首先得到一个 randomly-generated table（我应该这样做），而不是 min-heap table ，我得到None值，如下：

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

有什么想法吗？也许我应该换一种方式，不是比较 l[i] 和 parent，而是比较 l[i] 和它的左右 children?

Answer 1

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

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

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

实际问题如下：

您的 parent、lchild 和 rchild 函数旨在对 index 起作用，但您在索引 [= 处传递 l 的值=17=] 到函数：parent(l[i])

由于列表中的值可能比可能的索引范围高得多，因此您会列表索引超出范围。您可能想直接传递索引。

此外：

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

我假设结果应该是这样的：

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

你的定义 returns 不同的值。

一些小事：

所有这些随机 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 不 return 列表但修改它 in-place。最后 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，我得到了结果：

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

在 Python 建造 MIN-HEAP

Building MIN-HEAP in Python

python

min-heap