Question

In heapsort we view an array as a binary tree using the following mapping: a[0] is the root of the entire tree and for element a[i], its left child is a[2i+1] and its right child is a[2i+2]. Answer the following questions for an array of size n. ( Answers in some cases may be in terms of n.)

a) What is the index of the parent a[i] for any i > 0?

b) What is the biggest index for which a[i] is not a leaf?

c) What is the smallest value of i for which a[i] is a leaf?

d) Suppose n is one billion. What is the exact height of the tree? (height = maximum path length root to some leaf, path length = # of nodes)

Answer 1

Here we take inital index as zero for all.

a) The formula to calculate index of the parent a[i] for any i>0 is : floor((i-1)/2)

b) The formula to calculate  the biggest index for which a[i] is not a leaf is : floor(n/2)-1

c) The formula to calculate  the smallest value of i for which a[i] is a leaf is : floor(n/2)

d) One billionn = 10^9 = N

formula for height of a complete binary tree (if root is not count in height)=> ceil(log 2(N+1))-1 [ log 2 mean log base 2]

=>ceil(log2(1000000000+1))-1

=>ceil(29.8973)-1 => 30-1 => 29

if root is count in height => ceil(log2(N+1)) [log 2 means log base 2]

=> 30

  

Generally ,root is not count in height as per wikipedia.