recategorized by
662 views
1 votes
1 votes
A min heap of size 2048  is stored on an array with array indices [1..2048] is stored and the minimum number of comparisons required to determine the maximum of element is _______.(Assume that we are allowed to access the array indexes)
recategorized by

1 Answer

4 votes
4 votes

Max element in min heap will present at leaf node.

Min heap has 2048 elements.

#leaf nodes = $\left \lceil 2048/2 \right \rceil$ = 1024

So in total min number of comparisons needed = 1024 – 1 = 1023

 

PS: Good thing to remember, In a binary heap of ‘n’ nodes there are exactly $\left \lceil n/2 \right \rceil$ leaf nodes.

Refer: https://stackoverflow.com/questions/40665736/how-do-you-prove-there-are-ceiln-2-leaves-in-a-binary-heap-of-n-nodes

edited by
Answer:

Related questions

2 votes
2 votes
1 answer
1
LRU asked Nov 3, 2021
814 views
The time required to determine the minimum element from the max heap of size O(log(n)) is given by
2 votes
2 votes
1 answer
2
LRU asked Nov 22, 2021
832 views
Number different of binary search trees which can be created with the elements {12, 34, 22, 43, 13, 45, 55, 94, 99, 23} with 45 as the root is___.
1 votes
1 votes
1 answer
3
LRU asked Oct 4, 2021
468 views
Worst case time required to construct a balanced BST given a sorted array of integers which can be inserted in any order
5 votes
5 votes
1 answer
4
LRU asked Nov 5, 2021
646 views
Given the following undirected graph, the cost of the minimal spanning tree of the graph is ____.