The "height of binary tree" slide should read "height of nearly complete binary tree." Regular binary trees may become unbalanced and thus not have a height of O(logn). Because heaps are nearly complete binary trees (which are balanced), we know that the height is O(logn).
Hey Michael! What a great video! This six minute video actually took me a few hours to really gain understanding. :D QQ: You state at 5:29 that the run time is O(n) but in each iteration of the for loop you call max_heapify which has a run time of log(n). Being that, shouldn't the runtime be 0(n * log(n))? Thank you?
@@劉梓堂 I believe it is still actually O(n), because the vast majority of the calls to max_heapify from build_max_heap happens right above the leaves, which makes it constant in those cases (since it doesn't have to recurse). I actually calculated the number of calls to max_heapify in total, with recursion, for up to ~2^1000 and it seems very linear. For ~2^1000 it is about 4*n calls, which is also the case already at 2^8.
I've got a dumb question which is why is the running time of build_max_heap O(n), n = len(a)? (refer to 5:29). In my opinion, the for loop is O(n) and inside each for loop is O(logn) to call max_heapify so in total, the time complexity would be O(nlogn), right?
This is not explained in the video, but here is my explanation: max_heapify is actually log(subtree size), and not log(n), as stated in the video. This is very important since almost all calls to max_heapify happen at the lower levels, which have small subtrees. In total, I believe there are about 4*n calls to max_heapify, also counting recursive calls. This was calculated with a recursive formula in excel up to n=2^1000.
I really enjoy the bite sized nature of your videos It really helps me understand the concept, and I then know about it for future research if need be Thanks a lot for your content
Build heap is O(n) because although heapify is O(log n) for a single node, most nodes are near the leaves and require much less work, leading to a total cost that sums to O(n)
"largest" is the index of the largest value (18) prior to the swap. So at the point where it recurses, "largest" is indeed the index of 9 (because 9 and 18 swapped places), which is correct.
Very helpful video. However, I don’t understand why the time complexity of max heapify is O(log n). Could you explain or provide any reference materials? Thank you for reading this comment.
Argument that build_max_heap() is O(n) because it has one loop is wrong, as it calls max_heapify which is O(logn) => total is O(nlogn).However it is true that it is possible to implement it in O(n), for proof please check Lecture 4: Heaps and Heap Sort from MIT.
With the implementation shown in the video, it is actually still O(n), because max_heapify is log(subtree size), not log(n), and the vast majority of the calls to max_heapify are on the bottom few layers.
u have to add other conditions as for left children of tree lying on node 0 will also fall on the same index 0 so we have to add condition to place it on index one and for index two it would be 1 so again problem
The "height of binary tree" slide should read "height of nearly complete binary tree." Regular binary trees may become unbalanced and thus not have a height of O(logn). Because heaps are nearly complete binary trees (which are balanced), we know that the height is O(logn).
If you are reading this comment, I would like to say thank you for your educational content. You helped me pass Algorithms with a grade of B.
Awesome! 👊🏼
Love your videos. Short, clear, and no frills.
Micheal is singlehandedly helping every single computer science student pass this exam
God bless
and every software engineer leetcoding out there
Absolutely appreciate your visual explanations!!!
thank you!
typo at 5:01
last line is max_heapify(a, 5, i)
instead it should be max_heapify(a, 10, i)
You're right! Sorry about that, @Naren Babu. Copy/paste error on my part. Thanks for pointing it out.
You always makes things clear
Bro, really thanks to give so clean a very good explained things, you're literally save my life
Hey Michael! What a great video! This six minute video actually took me a few hours to really gain understanding. :D QQ: You state at 5:29 that the run time is O(n) but in each iteration of the for loop you call max_heapify which has a run time of log(n). Being that, shouldn't the runtime be 0(n * log(n))? Thank you?
It doesn't run n times it runs n-1 times so it should be n-1*logn
@@DannyJoseph n-1 = n in terms of algorithm complexity
Same though, I think that it's 0(n * log(n))
@@劉梓堂 I believe it is still actually O(n), because the vast majority of the calls to max_heapify from build_max_heap happens right above the leaves, which makes it constant in those cases (since it doesn't have to recurse). I actually calculated the number of calls to max_heapify in total, with recursion, for up to ~2^1000 and it seems very linear. For ~2^1000 it is about 4*n calls, which is also the case already at 2^8.
@@Zicrus "O(n), because the vast majority of the calls" Big-O is worst case, Theta is average case. So it's Theta(n), but O(nlogn)
Amazing! Very straight to the point
It would be great if you can also show methods for adding elements into the heap and removing them and the complexities involved there. Thanks!
Very clear explanation. Thanks very much!
I've got a dumb question which is why is the running time of build_max_heap O(n), n = len(a)? (refer to 5:29). In my opinion, the for loop is O(n) and inside each for loop is O(logn) to call max_heapify so in total, the time complexity would be O(nlogn), right?
This is not explained in the video, but here is my explanation:
max_heapify is actually log(subtree size), and not log(n), as stated in the video. This is very important since almost all calls to max_heapify happen at the lower levels, which have small subtrees. In total, I believe there are about 4*n calls to max_heapify, also counting recursive calls. This was calculated with a recursive formula in excel up to n=2^1000.
I really enjoy the bite sized nature of your videos
It really helps me understand the concept, and I then know about it for future research if need be
Thanks a lot for your content
Thanks! Very useful video, it clarified some things for me
I don’t understand why build max heap is not nlogn in run time since u run max heapify on n nodes
Build heap is O(n) because although heapify is O(log n) for a single node, most nodes are near the leaves and require much less work, leading to a total cost that sums to O(n)
Oh yeah, another addition to collection of golden clasics
I think there is a mistake at 3:24, for 9 to float down we need to keep using i in the recursive max_heapify, not the largest which is now 18
"largest" is the index of the largest value (18) prior to the swap. So at the point where it recurses, "largest" is indeed the index of 9 (because 9 and 18 swapped places), which is correct.
It was very helpful. thanks!!
Very helpful video. However, I don’t understand why the time complexity of max heapify is O(log n). Could you explain or provide any reference materials? Thank you for reading this comment.
whats the purpose of l
just a little doubt, in maxheapify shouldnt it be if la[largest]
In max_heapify, shouldn't it be if la[largest], since you're setting largest to i anyways? I guess it works as-is but just for consistency?
shouldnt it be -1 rather than 0 in the second parameter of the for loop ?
Argument that build_max_heap() is O(n) because it has one loop is wrong, as it calls max_heapify which is O(logn) => total is O(nlogn).However it is true that it is possible to implement it in O(n), for proof please check Lecture 4: Heaps and Heap Sort from MIT.
With the implementation shown in the video, it is actually still O(n), because max_heapify is log(subtree size), not log(n), and the vast majority of the calls to max_heapify are on the bottom few layers.
Why does the examples uses null as the first index in the array?
is it necessary on all heap algorithms?
check my notes here: github.com/msambol/dsa/blob/master/data_structures/heap.py#L39
@@MichaelSambol Thanks, and great videos!
I dont get the part where we get left and right indexes in heapify. Why arent they l = 2*i + 1 and r = 2*1 + 2?
Because he's indexing from 1 instead of from zero.
ur video is awesome!
Damn, this guy sounds like the Lord
What do you do with the intersect of maxheap, and minheap, where there is a fuzziness between these two properties?
Why you start the array with 1
u have to add other conditions as for left children of tree lying on node 0 will also fall on the same index 0 so we have to add condition to place it on index one and for index two it would be 1 so again problem
If your array starts with 0
left = 2i + 1
right = 2i + 2