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.

Micheal is singlehandedly helping every single computer science student pass this exam

Love your videos. Short, clear, and no frills.

Bro, really thanks to give so clean a very good explained things, you're literally save my life

Absolutely appreciate your visual explanations!!!

I don’t understand why build max heap is not nlogn in run time since u run max heapify on n nodes

typo at 5:01 last line is max_heapify(a, 5, i) instead it should be max_heapify(a, 10, i)

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!

You always makes things clear

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 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

Amazing! Very straight to the point

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

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.

just a little doubt, in maxheapify shouldnt it be if la[largest]

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?

Oh yeah, another addition to collection of golden clasics

It was very helpful. thanks!!

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?

shouldnt it be -1 rather than 0 in the second parameter of the for loop ?

whats the purpose of l

ur video is awesome!

Why does the examples uses null as the first index in the array? is it necessary on all heap algorithms?

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