# Build a max heap and Iteration

11,814

1:

``````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.

Share:
11,814

Author by

Updated on June 14, 2022

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?

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?
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?