from math import log

def pretty_print_heap(A):
    n = len(A) - 1 # the heap starts at position 1, so A[0] is ignored
    for h in range(int(log(n,2))):
        nspc = (2**(int(log(n,2)) - h + 1) - 2)
        line = nspc * ' '
        for i in range(2**h, 2**(h+1)):
            line += repr(A[i]).ljust(2) + (2*nspc + 2)*' '
        print line
    line = ''
    for i in range(2**(int(log(n,2))), n+1):
        line += repr(A[i]).ljust(2) + '  '
    print line

pretty_print_heap(range(0,20))

def parent(i):
    return int(i / 2)

def left(i):
    return 2 * i

def right(i):
    return 2 * i + 1

A = [0, 16, 7, 10, 8, 14, 9, 3, 2, 4, 1]
pretty_print_heap(A)

A = [0, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
pretty_print_heap(A)

def max_heapify(A, i, trace=True):
    if trace: # este código solo se ejecuta si trace==True
        print "-----------------------"
        print "i =", i
        print A
        pretty_print_heap(A)
    l = left(i)
    r = right(i)
    if l <= (len(A)- 1) and A[l] > A[i]:
        largest = l 
    else: 
        largest = i
    if r <= len(A)- 1 and A[r] > A[largest]:
        largest = r
    if largest <> i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest, trace)


max_heapify(A, 1)

def build_max_heap(A, trace=False):
    for i in range(int(len(A) / 2), 0, -1):
        if trace:
            # The next 4 lines of code just print the heap
            print "-----------------------"
            print "i =", i
            print A
            pretty_print_heap(A)
        max_heapify(A, i, trace=False)


A = range(11)
build_max_heap(A, trace= True)


def heap_sort(A):
    B = []
    build_max_heap(A)
    while len(A)>1:
        maxim = A[1]
        A[1] = A[-1]
        del A[-1]
        B.insert(0,maxim)
        print B
        max_heapify(A,1,trace=False)
    return B
        
print heap_sort([0,4,6,7,2,5,9])

def extract_max_heap(A):
    maxim = A[1]
    A[1] = A[-1]
    del A[-1]
    max_heapify(A,1,trace=False)
    return maxim
    
A = [0, 16, 7, 10, 8, 14, 9, 3, 2, 4, 1]

build_max_heap(A)
pretty_print_heap(A)


while len(A)>2:
    print "-----------------------"
    print "Extracted element:", extract_max_heap(A)
    pretty_print_heap(A)
    
    

def increase_key_heap(A,i,v):
    if A[i]>v:
        print "Error"
    A[i] = v
    print "-----------------------"
    print "Changed heap:"
    pretty_print_heap(A)
    
    while i>1 and A[i>>1] < A[i]:
        A[i>>1], A[i] = A[i], A[i>>1]
        # The next 4 lines of code just print the heap
        print "-----------------------"
        print A
        pretty_print_heap(A)
        print "i =", i
        ##############################################
        i = i>>1

A = [0, 16, 7, 10, 8, 14, 9, 3, 2, 4, 1]

build_max_heap(A)
pretty_print_heap(A)

increase_key_heap(A,7,17)


    

def insert_heap(A,v):
    A.append(v-1)
    increase_key_heap(A,len(A)-1,v)
    
A = [0, 16, 7, 10, 8, 14, 9, 3, 2, 4, 1]

build_max_heap(A)
pretty_print_heap(A)

insert_heap(A,18)