Build Heap Algorithm | Proof of O(N) Time Complexity

CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

========================================================================
Join this channel to get access to perks:

=======================================================================
USEFUL LINKS:

RELATED LINKS:

#heap #buildheap #techdose

[E__ShameemahamedS-bxed]

Don't stop making videos even if you have low subs your content is useful for many of us

[vedantsharma]

Very few tutors go in such depth to explain the proof. This is some seriously amazing content. Everything was crystal clear.

[dhzgdqd]

This is one of those proofs where it's not intuitive at all, but you have to accept it because the math is clear. Good explanation.

[omsaran]

Very few lectures explain the reason for steps in such detail, conciseness, clarity and intuition, all at the same time. I'm glad I got this video when I searched for this topic. Thank you!

[n.h.son]

Thank you for explaining the time complexity of building a heap that I've been struggling with

[biplawkumarsingh]

Read this concept from CLRS(after watching MITOCW videos on Heaps) and have to say your videos made it much more clear

[pallavijorapur]

Such a detailed explanation made me understand the concepts very clearly. Thank god I came across your videos on heap sort!! Please keep posting such videos!! :)

[AMITKUMAR-djfv]

I have another approach to find time complexity of heapify algorithm,
suppose we are present at level 'x' (level 0 at root) and my total height of tree is h(h=logn, where n is total number of node in tree)
then for heapify an element at level x we have to do h-x operation(in worst case) and in worst case it is required to heapify all the element at level x, and total number of element at level x is 2^x, so we have to do {2^x(h-x)} operation to heapify all the element at level x.
so my answer is summation x ranges from 0 to logn(as there could be logn number of levels) and (2^x(h-x)), here we can put h = logn.
this summation can be easily solved as first term (2^x*h) is simple G.P and second term (2^x*x) is simple AGP.
from above time complexity comes out to be O(n+logn) we can be written as O(n) as (n>logn).

[ronylpatil]

I used to be very scared of data structure but when I started watching your videos I started getting interested in it and your videos are very knowledgeable and in every video I learn something new.

[MatUserName]

You are passionate. It is nice to view your content when we need a deeper look.
I'm currently implementing an eikonal solver for the acoustic wave equation and this min-heap is fundamental to get it working right.
Thanks a million for your work.

[unnaipoloruvan]

Best video for heap so far i came across

[siddharth.chandani]

For those who are not able to understand (like me ) the formula at 8:54, Here 'h' means height of that level & 'N' means size of the heap..
In this e.g. N=15 and for h=0 (L3), max. no. of nodes = ceil(15/2^0+1) = ceil(7.5) = 8

[HaribhanSingh]

Best Video on the internet regarding heaps

[ankitshaw]

Nice explanation so much for all your efforts.

[sohammehta]

Bro, whole video is very good, but I found very much interest in the proof at the end.... nicely explained!! Thanks a lot!!

[praveennarvaneni]

Thanks for the in detail explanation of why we need to run the heapify only for internal nodes

[anveri]

For those who know the heapfiy algorithm and want to head straight to time complexity, skip to 7:19

[andrewcenteno]

This explanation was incredible. I was struggling to understand why It is O(n).

[einsteinxavier]

Excellent explanation for proof of O(N) time complexity

[anonanon]

It's indeed a good explanation. thanks