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)
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.
Get Answers For Free
Most questions answered within 1 hours.