0

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

所以我有父母，左孩子和右孩子的定义，考虑到从0开始的python编号列表元素：

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 用于将表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：好的，所以我已经修复了 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 来确定它是否有效......但它没有。它两次返回相同的列表，没有编译错误或任何东西。知道如何解决吗？

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)

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

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

有任何想法吗？也许我应该换一种方式来做，不是将 l[i] 与父母进行比较，而是将 l[i] 与左右孩子进行比较？

4

2 回答 2

3

所以我在 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
于 2016-01-23T21:17:31.443 回答
2

起初：parent您的,lchild和rchild功能有问题：

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

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

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

实际问题如下：

您的parent,lchild和rchild函数旨在用于 anindex但您将lat index的值传递i给函数：parent(l[i])

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

此外：

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

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

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

您的定义返回不同的值。

一些小事：

  • 所有这些随机int演员都是无用的。铸造一个inttoint什么都不做。唯一真正需要强制转换的行是：``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您将 index0处的值与 处的值进行比较parent(0) == -1。这包含了列表，可能不是您想要的。由于索引0没有父级，因此您不应尝试将其与其父级进行比较。

编辑2

bkop不返回列表，而是就地修改它。就print(l)在最后。您将看到原始列表已被修改。

于 2016-01-23T15:02:59.887 回答