2.7k views

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 | 2.7k views
0
wont it be lon n bcoz we can min heapify which takes log n and then we can extract root
+1

^^ 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)

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
0
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?
+11
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.
+8

@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

+1
but O(n) is searching for leaf nodes.

then how to go root to leaf if u not take (log n) as complexity?
+4
@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?
+3
@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?
+2
yes :)
0
@ arjun sir ...why it cant be logn

reason:

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

no need to reconstruct the heap
+1
Too much logic applied.

You try to perform heapify on n/2 nodes then how it take time O(logn ) .
0
yes heapify takes logn time only
+8
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)
0
@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
Convert the heap into array and do linear search that comes O(n).
0
If you are converting heap into array then why to do Linear search?

1
2