retagged by
20,578 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

Best answer
48 votes
48 votes
  1. $O(n)$

    In a max heap, the smallest element is always present at a leaf node. Heap being a complete binary tree, there can be up to $\frac{n}{2}$ leaf nodes and to examine all of them we would need $O(n)$ time.
edited by
4 votes
4 votes

The smallest element in a max heap would always be in the last level. => Search all leafs.

No. of leafs = No. of internal nodes + 1.

In an asymptotic sense, we can say No. of leafs = No. of internal nodes. If total nodes = n, leafs = $O(\frac{n}{2})$ = Internal nodes.

And, $O(\frac{n}{2}) = O(n)$

So, Option A.

3 votes
3 votes
Convert the heap into array and do linear search that comes O(n).
0 votes
0 votes

In a max heap, minimum value will be at the leaf nodes. Hence we will have to run a for loop from n/2 to n and check sequentially.

The time complexity of one for loop from n/2 to n will be O(n).

Hence option A. 

Answer:

Related questions

19 votes
19 votes
1 answer
4
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, ...