in DS retagged by
17,352 views
38 votes
38 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)$
in DS retagged by
17.4k views

4 Comments

edited by
Will it be correct to assume that the heap is stored in the form of an array?

If it is so, then we can apply binary search on the last $\left \lceil \frac n2 \right \rceil$elements (representing the leaf nodes) to get the minimum element, which results in $log\left ( \frac n2 \right )$ =$O\left ( log n \right )$ time complexity.

Edit: My bad. Just realized that the last $\left \lceil \frac n2 \right \rceil$ elements are not in sorted order, so can’t apply binary search without sorting them.
1
1
@sammanv how much time do u think one pass of selection sort will take ?? o(1) or o(n)
0
0
@Yogesh88 yes, I was wrong, it will take O(n)
0
0

5 Answers

44 votes
44 votes
Best answer
  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 Comments

convert the max heap to minheap  

will always take O(n) time.

2
2

@srestha $ma'am$ can you please guide me why is it or how is it taking $O(n)$ time.

As I was thinking that we already have a MAX heap with us, now we can make use of MIN-heapify to get MIN heap

MIN-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ A.heap-size and A[l] < A[i]
        smallest = l
    else smallest = i
    if r ≤ A.heap-size and A[r] < A[smallest]
        smallest = r
    if smallest != i
        exchange A[i] with A[smallest]
        MIN-HEAPIFY(A, smallest)
0
0
Heap is complete or almost complete binary tree. It will never be skewed....
0
0
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.

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

2 Comments

If you are converting heap into array then why to do Linear search?
0
0
there is no need of linear search,we know the leaf in a heap will be present at floor(n/2+1) to n. just put the heap into array and directly search the array from that position. in worst case it will be o(n/2)=o(n)
0
0
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