retagged by
20,577 views
44 votes
44 votes

In a binary max heap containing $n$ numbers, the smallest element can be found in time 

  1.  $O(n)$
  2.  $O(\log n)$
  3.  $O(\log \log n)$
  4.  $O(1)$
retagged by

5 Answers

0 votes
0 votes
In n element max heap, smallest element is one of the leaf.. in array representation of max heap, leaves index start from floor(n/2)+1 to n. And there will be max n/2 elements present at last level (height 0).

 

Just do a for loop from floor(n/2)+1 to n

In which keep track of smallest element

There will be O((n/2)-1) = O(n) comparisons ( we need only 1 element to find)..

Answer =A
Answer:

Related questions

19 votes
19 votes
1 answer
8
Ishrat Jahan asked Oct 31, 2014
6,178 views
Which of the following sequences of array elements forms a heap?$\{23, 17, 14, 6, 13, 10, 1, 12, 7, 5\}$$\{23, 17, 14, 6, 13, 10, 1, 5, 7, 12\}$$\{23, 17, 14, 7, 13, 10, ...