Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Number of comparisons in build_heap

View gist:1020043
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.