2

我有两个问题：

1）最近我正在尝试建立一个最大堆。即使我阅读了CLRS，我在运行它时也找不到错误。以下是我的代码...

def maxHeapify(list, index):
    int = index
    left = (int+1) * 2 - 1
    right = (int+1) * 2
    largest = 0
    if left < len(list):
        if (left <= len(list)) & (list[left] >= list[int]):
            largest = left
        else: 
            largest = int
    if right < len(list):
        if (right <= len(list)) & (list[right] >= list[largest]):
            largest = right
    else:
        pass
    if largest != int:
        listNew = swapWithinList(list, int, largest)
        listNew = maxHeapify(listNew, largest)
    else:
        return listNew


def swapWithinList(list, id1, id2):
    num1 = list[id1]
    num2 = list[id2]
    listNew = list[:id1]
    listNew.append(num2)
    listNew = listNew + list[(id1+1):id2]
    listNew.append(num1)
    listNew = listNew + list[(id2+1):]
    return listNew

我提供输入，但控制台只是说：

UnboundLocalError: local variable 'listNew' referenced before assignment

这是否意味着我将 return 语句放在错误的行上或者我没有提到的东西？

2）什么是迭代？

当我问这个问题时，我有点尴尬。但什么是迭代？维基说这个过程的每次重复都意味着它，那么它是循环给每一轮的结果吗？

而迭代器似乎是Python中的一个基本元素，迭代器和迭代有什么区别？

4

2 回答 2

6

1：

无需进一步评论，以下是改编自Wikipedia的代码：

def max_heapify(A, i):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    if left < len(A) and A[left] > A[largest]:
        largest = left
    if right < len(A) and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def build_max_heap(A):
    for i in range(len(A) // 2, -1, -1):
        max_heapify(A, i)

例子：

def ptree(A, i=0, indent=0):
    if i < len(A):
        print '  ' * indent, A[i]
        ptree(A, i * 2 + 1, indent + 1)
        ptree(A, i * 2 + 2, indent + 1)

A = range(9) 
build_max_heap(A)
ptree(A)

结果：

 8
   7
     3
       1
       0
     4
   6
     5
     2

如果你有问题就告诉我们。

2：

从技术上讲，python 中的迭代是一个重复调用某个对象的next()方法直到引发StopIteration异常的过程。拥有此next方法的对象称为迭代器。能够为调用代码提供 Iterator 的对象称为 Iterable。

于 2012-10-30T15:18:40.643 回答
0

问题在这里：

if largest != int:
        listNew = swapWithinList(list, int, largest)
        listNew = maxHeapify(listNew, largest)
    else:
        return listNew

如果 if 语句为假，则尝试返回 listNew，但此时 listNew 可能不存在（仅当 if 语句为真时才分配给它）。

一次迭代只是通过一个循环，或者一般来说，一次通过一些更大的东西。迭代器是遍历数据结构的对象，或者一次遍历一个元素。

于 2012-10-30T15:19:36.267 回答