public
Last active

Number of comparisons in build_heap

  • Download Gist
gistfile1.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
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))

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.