The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.6k 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)$

 

asked in DS by Loyal (4.3k points)
retagged by | 1.6k views
wont it be lon n bcoz we can min heapify which takes log n and then we can extract root

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

2 Answers

+26 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.
answered by Boss (6.3k points)
edited by
why it will be o(n), heap cannot be skewed tree, and complexity of heap is o(n log n) right?
whats the answr?
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.

@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 

but O(n) is searching for leaf nodes.

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

reason:

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

 

no need to reconstruct the heap
Too much logic applied.

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

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,688 questions
40,231 answers
114,272 comments
38,803 users