The intuition is: Most of the nodes will be leaves nodes, which do not need to be heapified. The longest number of steps will be for the nodes higher up in the tree, but of these there are only a few. So half of the nodes can stay, of the rest half only need one step, of the rest half only need 3 steps, etc. Only the root node needs potentially log(n) steps and there is only one root.
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!
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.
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).
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.
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!! :)
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
what i dont understand is why he changed the numbering of height... in the previous videos he did height 0 the root height 1 have 2 nodes height 2 have 4 nodes height 3 has 8 nodes THEN NOW he did the exact opposite why?? if you do it 0 1 2 3 then it would be ceil(15/2^(3+1)) = ceil(15/16) obviously very wrong lol in his previous videos he shown us that height of tree = floor(logN)
9:43 In complete binary tree the no. of nodes only in the last level will be < floor ( N / 2^(h+1)) right?.. The nodes in the internal levels are always equal to floor ( N / 2^(h+1)) as in binary tree right?
At 9:30, you mention that for an almost complete binary tree, the maximum number of nodes is less than the ceil of N / 2^(h+1). Now I consider an almost complete binary tree with 8 nodes, level 1 has 4 nodes, while your formula shows that the maximum number of nodes at level 1 is less than ceil of 8 / 2^(1+1) = 2. Maybe I misunderstood something. Many thanks for an explanation!
We do not consider N to be nodes at particular level. N is the total number of nodes. Level 1 has height = 2 and leave nodes have height zero. In your case, 15/2^(2+1) =2 and the number of nodes at level 1 is equal to 2 as well, as it should be. I hope it was helpful.
Hi do we need to maintain a copy of the array? because when reach last idx of 0 having element 3. we have previously swapped it with 9. so it won't have idx 0 as 9 will now have idx 0.????
you considered height from top in previous videos.. and here you are considering it from below.. I'm a bit confused.. What should we consider as 'height' ?
this is so confusing because now you suddenly swapped what height is before you numbered height as root being height 0 then height 1 height 2 height 3 now you doing the exact opposite and calling the root as height 3? then on left side you noted them with L0 L1 L2 yet calling root L1 even tho its L0 aka level 0 very confusing, if you note height in one way first then different next time it wont make sense to anyone
Good video but your writing is not very clear. Better use computer text instead. Cant read anything. And your camera hides some text in some sequences for example at 2:25
Very few tutors go in such depth to explain the proof. This is some seriously amazing content. Everything was crystal clear.
Thanks :)
Don't stop making videos even if you have low subs your content is useful for many of us
Sure bro :)
🥺 yesss
@@yutaitadori7318 :)
yes..and thanks for making such well explained videos
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.
The intuition is: Most of the nodes will be leaves nodes, which do not need to be heapified. The longest number of steps will be for the nodes higher up in the tree, but of these there are only a few. So half of the nodes can stay, of the rest half only need one step, of the rest half only need 3 steps, etc. Only the root node needs potentially log(n) steps and there is only one root.
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!
Welcome 😀
Read this concept from CLRS(after watching MITOCW videos on Heaps) and have to say your videos made it much more clear
Great :)
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.
Best Video on the internet regarding heaps
Thanks for the in detail explanation of why we need to run the heapify only for internal nodes
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).
he did using height and u are taking ur level as the depth(because level 0 at root means depth 0 at root)
Amazing
Best video for heap so far i came across
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.
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!! :)
Welcome :)
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
what i dont understand is why he changed the numbering of height... in the previous videos he did height 0 the root height 1 have 2 nodes height 2 have 4 nodes height 3 has 8 nodes THEN NOW he did the exact opposite why??
if you do it 0 1 2 3 then it would be ceil(15/2^(3+1)) = ceil(15/16) obviously very wrong lol
in his previous videos he shown us that
height of tree = floor(logN)
Thank you for explaining the time complexity of building a heap that I've been struggling with
Welcome :)
Bro, whole video is very good, but I found very much interest in the proof at the end.... nicely explained!! Thanks a lot!!
Welcome :)
This explanation was incredible. I was struggling to understand why It is O(n).
Nice explanation .....ThankYou so much for all your efforts.
Welcome :)
Thank you so much for these videos
Welcome :)
Very nice explanation
Thanks ☺️
Great explanation!
great channel to learn concepts in depth
👌🏼
Excellent explanation for proof of O(N) time complexity
For those who know the heapfiy algorithm and want to head straight to time complexity, skip to 7:19
Thank you for such a detailed explanations. You're awesome.
clear and concise information, thank you so much
thank you sir for good explanation .
Welcome :)
It's indeed a good explanation. thanks
Welcome
WOW thanks for the proof, before that I was literally assuming that the time complexity of build heap is O(NlogN)
Same here. And after watching the proof at the end of the video, I’m completely convinced that the time complexity of heapify would be O(n)
Very nice explanation bro thanks
Hare Krishna..! I love your explanation
8:00 the crux + proof of why heapify is O(N) and not O(N log N)
Nice video. Thanks for the explanation. Why space complexity is not O(1)? You are effectively just swapping elements within the array in place.
Super video! I applauded for ₹100.00 👏👏
Thanks for your support ❤️
Awesome job
9:43 In complete binary tree the no. of nodes only in the last level will be < floor ( N / 2^(h+1)) right?.. The nodes in the internal levels are always equal to
floor ( N / 2^(h+1)) as in binary tree right?
8:04 actual proof starts
👍🏼
I'm satisfied with the proof on the time complexity. What about the space complexity? May I ask why it is O(logN)?
log N is the height of the tree. we are building heap inplace
Thank you so much
7:29 It is Log N to the base 2
In this video 08:45 ht should be 0 1 2 3 ?
I could see reverse order here.
I watched previous video there it is ht = 0 1 2 3
thanks for this video
At 9:30, you mention that for an almost complete binary tree, the maximum number of nodes is less than the ceil of N / 2^(h+1). Now I consider an almost complete binary tree with 8 nodes, level 1 has 4 nodes, while your formula shows that the maximum number of nodes at level 1 is less than ceil of 8 / 2^(1+1) = 2. Maybe I misunderstood something. Many thanks for an explanation!
We do not consider N to be nodes at particular level. N is the total number of nodes. Level 1 has height = 2 and leave nodes have height zero. In your case, 15/2^(2+1) =2 and the number of nodes at level 1 is equal to 2 as well, as it should be. I hope it was helpful.
@@adhaarsharma753 15 // 2^(2+1) is not 2. It is 1. Surely the formula is incorrect.
@@adhaarsharma753 my bad. I’m mixing up the floor and ceil function
you didnt explain, how a height h, will have max Nodes as ceil ( N/ 2^(h+1))
because he did it wrong again he did height backwards... in previous video he did height as 0 1 2 3 while in this video he did 3 2 1 0 for no reason
Sir, how did we get rid of the ceil operator while deriving the proof? time 12:40
Hi do we need to maintain a copy of the array? because when reach last idx of 0 having element 3. we have previously swapped it with 9. so it won't have idx 0 as 9 will now have idx 0.????
Just wow!!! Keep it up.
can u plz explain why 4 * N space required for segment tree
I will do it when I resume Segment tree.
sir can you please make a video on tiling problems (most importantly 3*n board filled by 2*1 shaped tiles)
Just a question why is the height of tree log n?
why we are considering the height in reverse order, like the height of 1st level should be 0, 1,2,3 not 3,2,1,0
just loved it
thank you very much !!!
what if we don't ceil and floor? what will be the issues?
you considered height from top in previous videos.. and here you are considering it from below.. I'm a bit confused.. What should we consider as 'height' ?
I think it is more appropriate to call it depth here instead of height.
Super video! I applauded for ₹40.00 👏
Thanks for your support ❤️
Sir can you please explain how you are taking O(h) a constant? It's dependent on height of a node but how can you take it as constant?
its not a constant, bro => since any constant * h ~ O(h)
thank you !!!
Ah, I see, the heapify algorithm in previous video is not make an entire max heap. We must use a loop to make entire tree max heap.
yep
hey. great content. just that your handwrithing is not readable at least to me. please type them or write them better
thanks!🤩
sir wehere is build heap code?
9:32
When no. of nodes is 1 , how can the height be 3 ?
height is calculated from ground because
why is it ok to take N out of sigma summation?
Variable is H.
@@techdose4u When h is log N, N and H change together. Why does it makes sense to treat N like a constant?
@@seans9096 when h is logN then N is fixed and only h changes
@@kasyapdharanikota8570 when h is logN, how come N is fixed but logN can change
@@seans9096 h=logN , means that we are choosing a specific value of N and that N will not change.
bhaiya aapka explanation amazing hai but sirf aapka aaawaz se dr lgta hai
where is the code?
sir, what if we followed the top-down approach as illustrated in the previous approach??? Was that also a way around??
previous video**
Top-down approach takes O(nlogn) compared to bottom-up which takes O(n)
this is so confusing because now you suddenly swapped what height is before you numbered height as root being height 0 then height 1 height 2 height 3 now you doing the exact opposite and calling the root as height 3? then on left side you noted them with L0 L1 L2 yet calling root L1 even tho its L0 aka level 0 very confusing, if you note height in one way first then different next time it wont make sense to anyone
Good video but your writing is not very clear. Better use computer text instead. Cant read anything. And your camera hides some text in some sequences for example at 2:25
😎
respect++;
you are Robot.
kitna kama lete ho youtbe se?