Heaps in 6 minutes — Methods

Step by step instructions for building a heap.

[MichaelSambol]

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

[turkialotibi]

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.

[DancingHippo]

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

[Fuego]

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

[narenbabu]

typo at 5:01

last line is max_heapify(a, 5, i)

instead it should be max_heapify(a, 10, i)

[BABEENGINEER]

Absolutely appreciate your visual explanations!!!

[josecalles]

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

[n.h.son]

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?

[govindrai]

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?

[balive]

Very clear explanation. Thanks very much!

[mfahmy]

In max_heapify, shouldn't it be if l<heap_size and a[l]>a[largest], since you're setting largest to i anyways? I guess it works as-is but just for consistency?

[jthkrlr]

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

[Singh-lu]

just a little doubt, in maxheapify shouldnt it be if l<heap_size and a[l]>a[largest]

[Xxnightwalk]

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

[WailingDarkness]

whats the purpose of l<heap_size t 3:16 . Also what's the difference between max_heapify and build_max_heap ?

[moriartyjames]

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.

[govindrai]

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!

[DemosthenesKar]

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

[NickWinters]

Thanks! Very useful video, it clarified some things for me

[aymanhww]

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