Build a max heap and Iteration

11,814

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.

Share:
11,814

Related videos on Youtube

lucasKo
Author by

lucasKo

Twitter: @lucaskointw

Updated on June 14, 2022

Comments

  • lucasKo
    lucasKo over 1 year

    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?

  • lucasKo
    lucasKo about 11 years
    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
    georg about 11 years
    @lucasKoFromTW: sorry, I meant the wikipedia article: en.wikipedia.org/wiki/Binary_heap
  • lucasKo
    lucasKo about 11 years
    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?

Related