254 views
I was going through the heap concept and one question came into my mind what will be the best case time complexity of finding the minimum element in a max heap?

Thank you:)
in DS | 254 views
+1
O(n)  assume that heap is stored in array and then we apply linear search.

for best case we still have to search entire heap.
+3
Minimum element in a Max heap will always be one of the leaf nodes of the heap.. Leaf nodes in heaps range from floor(n/2)+1  to n. So in the worst case we need to check n/2 elements. So time complexity is O(n).
0

@Satbir

Ok i got it ...

One more thing will you please explain me what is the relation between the heap sort and heapify...

heapsort ===> O(nlogn)

heapify  ====> O(n)

Why not the heapsort cost O(n^2)

For sorting

1) First we apply heapify === O(n)

2) Delete the root element (store it )and repalce it with the last node

3) repeat 1 and 2

so it will take O(n*n) time as we are doing heapify for n times...

please help me out with this .... I have watched many videos but I am still confused

Thank you:)

+1

Max heapify :-

• In this we have a tree in which both left and right subtree are already heap but root is not following heap property.
• So we swap root with with either left or right child ( whichever is the greatest) and then follow the procedure on the swapped child.
• At each level we have to select the left or right child so T.C. = O(2*log n) = O(log n).

----------------------------------------------------------------------------------------------------------------------------------------

Heapsort :-

• we are given a tree which is a heap.
• we remove the top element and replace it with leaf element.
• then we apply max heapify so that the tree again becomes a heap but this time the tree  will have 1 element less. i.e. highest value is selected and eliminated.

again we do the same step as mentioned above (

• we remove the top element and replace it with leaf element.
• then we apply max heapify so that the tree again becomes a heap but this time the tree  will have 1 element less. i.e. highest value is selected and eliminated.

)

again we do the same step

..........

we do it till the tree is empty.

=> we apply max heapify n times
=> T.C. = n * O(log n) = O(n log n )

+1
Consider a min heap.

When one element is deleted , and you take an element from the right most leaf and place it at root.

Now think , do u need to check with all the elements , and both the sub trees? No right?

So time complexity of heapification is O(h) .

Asymptotically each deletion will cause heapification to take place , and each heapification would take log(n) time .
0
Thank you guyz for making it clear.....

So, is the correct procedure

1] there is an unsorted array

2] we build a max heap (using max heapify but for elements from Array to Array[floor(n/2)]) out of that unsorted array in O((n/2)*logn) i.e. O(n*logn) time

3] Then the root(first)element is deleted and stored  in O(1) time and last element from the array is placed in root.

4]Again we perform the max heapify but this time only on the root node (and not like step 2 where we have to hapify the whole array) this will take O(logn) time

5] repeat step 3] and 4] for all n (n is number of elements)  O(n*logn)

So, total time taken = O(n*logn(step2) + n*logn(step5))=O(n*logn)

Correct me if I am wrong

And again, thanks for the help... it really means a lot :)
0
buildng a max heap using heapify takes O(n) time.
0

https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/

have a look hear , i think it will still take O(n logn)

+1
It's O(n) only if elements are present . If elements are being added one by one then it will be O(nlogn)
0

Hence Proved that the Time complexity for Building a Binary Heap is .

check again bro.see this last line of that post.

0
It's the best complexity possible . But this is only possible when we already have the elements present , can you say for sure than it will be O(n) if the heap is being from the scratch and elements are being added to the heap one after another?
0
But if we are having an array of elements , then also we hepify by adding element one by one from Array[floor(n/2)])  to Array

then the time complexity will be O(nlogn)

....

will you please give an example for O(n) time required
0
O(n) is possible , and there's a mathematical proof for it too , but this case exists only if we have an existing complete binary tree . It wont be a case when heap is being built by adding elements to heap one by one
0
So what to write in exam

O(n) or O(nlogn)

if this question drops
0

read the post mentioned above ....we are always provided with an unsorted array of elements and we build heap from it in O(n) time.

remember : - build heap O(n), heapify O(log n) and heapsort O(n log n ) each have different complexity.

0

@prashant jha 1

A quick look over the above algorithm suggests that the running time is , since each call to Heapify costs and Build-Heap makes such calls.
This upper bound, though correct, is not asymptotically tight.

0

You are correct there .

we are always provided with an unsorted array of elements and we build heap from it in O(n) time.

Only if we're provided with an array right?

It's the best possible.

0

https://en.wikipedia.org/wiki/Binary_heap

I quote from it :-

Building a heap from an array of n input elements can be done by starting with an empty heap, then successively inserting each element. This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n log n) time: it performs n insertions at O(log n) cost each.[a]

However, Williams’ method is suboptimal. A faster method (due to Floyd) starts by arbitrarily putting the elements on a binary tree, respecting the shape property

0

It's the best complexity possible . But this is only possible when we already have the elements present , can you say for sure than it will be O(n) if the heap is being from the scratch and elements are being added to the heap one after another?

its the worst complexity possible. O(n) denotes worst case complexity.

0
O(n) is worst? 😲 Then why people went for it?

Then what is O(nlogn) ?
0

@prashant jha 1

The case which you are mentioning will have a time space trade off because we are keeping input elements in one array and making heap in other array. so O(n) extra space would be required and that is also not the build heap algo.

that algo is william's method.

0
Bhai theek hai _/\_ :)
0
I think he meant best case complexity O(n)

edit: So, O(n) is the time taken for building a heap

that's the conclusion .
+1

conclusion : -

building heap by williams method takes O(nlogn) time. it does not uses max heapify technique.

building heap using max heapify takes O(n) time.

@prashant jha 1

@Nandkishor3939

thanks for the discussion.

+1 vote
Minimum element in a Max heap will always be one of the leaf nodes of the heap.

Leaf nodes in heaps range from $\left \lfloor \frac{n}{2} \right \rfloor+1$  to $n$.

so in the worst case we need to check $\frac{n}{2}$ elements.

$\therefore$ time complexity is $\Omega (n)$ for finding minimum element in a max-heap in worst case.

OR

Assume that heap is stored in array and then we apply linear search on the second half of the array since all the leaf nodes will be in second half of the array

So T.C. = $\Omega (\frac{n}{2}) = \Omega(n)$
by Boss (21.6k points)
edited by
0
You should change best to worst case and big O to big Omega to make it precise.