3

我正在编写一个在 Python 中“堆积”列表的 O(n) 算法。我不明白为什么它不起作用。

def func(l):
    size=len(l)
    for root in range((size//2)-1,-1,-1):
        child = 2*root+1 #parent of child is target
        while(child<size):
            #l[child] should be smaller sibling
            if child<size-1 and l[child]>l[child+1]:
                child+=1
            #can we put l[root] in l[child//2]?
            if l[root]<=l[child]:
                break #yes
            #no
            l[child//2]=l[child]#move child up
            child=2*child+1#move down a level
        l[child//2]=l[root]
    return l
4

2 回答 2

3

您的功能有两个问题。

第一个很容易掌握。您使用错误的计算来查找child索引的父级。而不是child // 2，您应该使用(child - 1) // 2. 这导致您将一些值转移到错误的位置。

第二个问题有点微妙。如果l[root]大于它的一个孩子，则您当前正在用该孩子覆盖它，因此当您尝试将其插入列表中稍后的另一个位置时，原始值不再可用。可能您应该保存l[root]在for循环的顶部，然后在您l[root]稍后在代码中检查的任何时候使用保存的值（循环if内部while和结束后的最终分配。

这是代码的固定版本，并带有注释以指出我所做的更改：

def func(l):
    size=len(l)
    for root in range((size//2)-1,-1,-1):
        root_val = l[root]             # save root value
        child = 2*root+1
        while(child<size):
            if child<size-1 and l[child]>l[child+1]:
                child+=1
            if root_val<=l[child]:     # compare against saved root value
                break
            l[(child-1)//2]=l[child]   # find child's parent's index correctly
            child=2*child+1
        l[(child-1)//2]=root_val       # here too, and assign saved root value
    return l
于 2014-04-16T03:36:11.227 回答
1

上面的解释很好，这是一个稍微修改过的版本：

 # heapify in place
 def heapify(A):
    # write your code here
    for root in xrange(len(A)//2 - 1, -1, -1):
        rootVal = A[root]
        child = 2 * root + 1
        while child < len(A):
            if child+1 < len(A) and A[child] > A[child + 1]:
                child += 1
            if rootVal <= A[child]:
                break
            A[child], A[(child - 1)//2] = A[(child - 1)//2], A[child]
            child = child * 2 + 1
于 2015-09-21T09:46:11.863 回答