Build a max heap and Iteration

Question

I have two questions:

1) Recently I'm try to build a max heap. Even though I read CLRS I can't find the bug as I run it. The following is my code...

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

I give input but the console just says:

UnboundLocalError: local variable 'listNew' referenced before assignment

does it mean that I put the return statement on the wrong line or there's something I haven't mentioned?

2) What is a iteration?

I am a bit embarrassed when I ask the question. But what is a iteration? Wiki says each repetition of the process means it, so is it a result the loop gives each round?

And iterator seems a basic element in Python, what's difference between iterator and iteration?

Solution

1:

Without further comments, here's the code adapted from 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)

Example:

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)

Result:

 8
   7
     3
       1
       0
     4
   6
     5
     2

Let us know if you have any questions.

2:

Iteration in python is technically a process of repeatedly calling some object's next() method until it raises the StopIteration exception. Object that possesses this next method is called Iterator. An object that is able to provide an Iterator for the calling code is called Iterable.

Comments

[lucasKo]

Thank you! So iteration is a process that keep calling the next() method, and I call iterator to execute the next() method. But what is the WP article? I google it and it turn out to be wordpress article?

[georg]

@lucasKoFromTW: sorry, I meant the wikipedia article: en.wikipedia.org/wiki/Binary_heap

[lucasKo]

Thanks! But after I modify the code, it prints out IndexError: list index out of range. I can't find the bug since the notation of left and right have nothing wrong. How can I fix the error?