recategorized by
447 views
0 votes
0 votes
A complete binary min-heap is made by including each integer in [1,1023][1,1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum value of integer at

a. ) First node of depth 8 is?

b.)  First node of depth k is?
recategorized by

1 Answer

Best answer
1 votes
1 votes

DataSet contains :1 to 15 elements.We need to find maximum possible value of first integer at depth 8 having root at depth 0.We insert elements 2 to 8 at right subtree of root   means half of the node at right subtree of root.After completion insert 9 and after that insert 10 to 12 at right subtree and so on.That mean whenever i have choice always try to insert smaller elements at right subtree of any node.

Now comes to the original question 1023 total elements and having 9 as max depth. as our example max depth is 3 and at depth 2 first element is 13 that is 15-2. Same way for 1023 elements at depth 8  maximum first element is 1023 -2=1021;

at depth 7 max first element =1023-2-4=1017 same as above example.This will continue.

at Depth 6 max first element=1023-2-4-8 =1009 

correct me!

selected by

Related questions

2 votes
2 votes
0 answers
1
S Ram asked Feb 1, 2017
564 views
how to solve this please explain procedure...
1 votes
1 votes
2 answers
3
ramakrushna asked Dec 26, 2021
498 views
I know the answer but need a good explanation for this question. Can anyone help. Thanks!
0 votes
0 votes
0 answers
4
bts1jimin asked Sep 10, 2018
1,827 views
What is the number of comparisons required to extract 45th element of the min heap?