Redirected
recategorized by
2,273 views
5 votes
5 votes
A min heap having 1024 distinct elements with keys ranging from 0 to 1023 is stored in array of 1024 indices. The maximum difference between the keys of all the element that can possibly be stored at (n/2)th index of the array is...........
recategorized by

2 Answers

1 votes
1 votes
There are 1024 elements, there will be total 11 levels, 512 is the middle element. minimum level possible is Level 2 because 0 is the minimum element, Root should be 0, in the second level we can have 512.

 

Maximum level possible is Level 11.

 

Difference is 11-2 = 9
0 votes
0 votes
since there are 1024 elements, there will be ceil{log(1+1024)}=11 levels, so in worst case, the 512 can be present at level 11(last level)

in best case the element  512 can be present only at level 2, it root is at level 1

then the difference = 11-2=9

Answer is 9

Related questions

0 votes
0 votes
1 answer
1
saurav raghaw asked Dec 22, 2018
674 views
The time complexity of the most efficient algorithm to determine whether an arbitrary array of size ‘n’, is min-heap or not?(A) O(log n)(B) O(n)(C) O(n logn)(D) O(1)
1 votes
1 votes
1 answer
2
gmrishikumar asked Dec 1, 2018
2,248 views
What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap?
1 votes
1 votes
1 answer
4
Rishabh Malhotra asked Feb 24, 2018
569 views
A min-heap contains $2^{(h + 1)} -1$ elements. If we randomly traverse the tree such that there is an equal probability of going left or right at each node, what is the p...