Number of comparisons in build_heap

gistfile1.py

def parent(i):
    return i/2
 
def left(i):
    return 2*i
 
def right(i):
    return 2*i+1
 
def heapify_cost(n, i):
    most = 0
    if left(i) <= n:
        most = 1 + heapify_cost(n, left(i))
    if right(i) <= n:
        most = 1 + max(most, heapify_cost(n, right(i)))
    return most
 
def build_heap_cost(n):
    return sum(heapify_cost(n, i) for i in xrange(n/2, 1, -1))