in DS retagged by
14,596 views
35 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
14.6k views

6 Comments

wont it be lon n bcoz we can min heapify which takes log n and then we can extract root
0

^^ So you want to convert this Max Heap into a Min Heap and extract min ?

Okay, do so.

1) Make Min Heap from Max Heap: O(n) How ?    Why O(n), shouldn't it be O(nlogn) ?

2) Extract Minimum: O(1)

3: Min Heapify: O(log n)

O(n) + O(1) + O(log n) = O(n)

4
Put all the elements of max heap in array and apply 1 pass selection sort. we can find it in O(1) time.Correct me if i m wrong..
0
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.
0
@sammanv how much time do u think one pass of selection sort will take ?? o(1) or o(n)
0
@Yogesh88 yes, I was wrong, it will take O(n)
0

5 Answers

40 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

20 Comments

why it will be o(n), heap cannot be skewed tree, and complexity of heap is o(n log n) right?
0
whats the answr?
0
Complexity of heap sort is $O(n \log n)$. Heap is never skewed- its complete binary tree. Still, there can be up to $\frac{n}{2}$ leaf nodes.
19

@arjun sir .   

In a max heap, the smallest element is always present at a leaf node. so for that we need to reach to leaf nodes that will take o(logn) time . after this bcz complete binary tree contain n/2 nodes on the leafs of tree .So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n/2)+logn so totaly worst case complexity is o(n) .   am  i  right  sir 

16
but O(n) is searching for leaf nodes.

then how to go root to leaf if u not take (log n) as complexity?
1
@rajan yes you are right.

@srestha yes, but that won't make a difference to answer - O(n) + O(log n) = O(n).

Also, if heap is implemented as an array, we can directly go to leaf - want to try it?
5
@Arjun sir

if we put heap element in an array

then first n/2 nodes are intermediate node and last floor(n/2)+1 are leaves

So, directly go to the last n/2 node and search one by one.

is it that direct approach?
7
yes :)
3
@ arjun sir ...why it cant be logn

reason:

convert the max heap to minheap  and find the root element
0
Asu design min heap itself take O(n) time using build heap
3
heap is already there just perform hepify at (n-1)/2th node  to root

 

no need to reconstruct the heap
0
Too much logic applied.

You try to perform heapify on n/2 nodes then how it take time O(logn ) .
1
yes heapify takes logn time only
0
In max heap, smallest element will be at leaf and we know leaf is from ceil(n/2) to n

To reach the leaf then it takes O(logn) time because height of heap can go upto logn(it is almost complete binary tree)

then we have to traverse from n/2 to n to reach the required element which will take O(n) time in worst case

hence TC = O(logn) + O(n)

                 =O(n)
10
@cse23, arjun sir yes i agree with u and the ans ...but my approach is just perform hepify on the internal nodes which can take logn time
0
But here it's not asked for any general element. For minimum can't we do like this

Smallest = min{left tree,  right Tree}

A recursion like this
0
edited by

@Prashant. @Arjun @srestha any mentor can any body tell me what @asu is saying I'm very confused how he got log(n) time ?

if you want to convert max heap  -> min heap to get min element you need to apply build_Min_Heap procedure(variant of Build_Max_Heap) isn't it and that takes again O(n) time starting from heap_size/ 2 to 1.

then how he got O(logn) ? 

tell me if there is any approach to solve it in O(logn) ?

0

convert the max heap to minheap  

will always take O(n) time.

1

@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
Heap is complete or almost complete binary tree. It will never be skewed....
0
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
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
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 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. 

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