The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2k 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 Active (3.7k points)
retagged by | 2k views
0
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)

2 Answers

+27 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 Loyal (6.1k points)
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?
+9
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.
+4

@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?
+2
@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
+7
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
+2 votes
Convert the heap into array and do linear search that comes O(n).
answered by Junior (561 points)
0
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

35,526 questions
42,802 answers
121,616 comments
42,166 users