Heaps in 6 minutes - Methods

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

[@turkialotibi7168]

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.

[@MichaelSambol]

Awesome! 👊🏼

[@DancingHippo]

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

[@MichaelSambol]

God bless

[@prpshrt]

and every software engineer leetcoding out there

[@Fuego958]

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

[@narenbabu629]

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

[@MichaelSambol]

You're right! Sorry about that, @Naren Babu. Copy/paste error on my part. Thanks for pointing it out.

[@BABEENGINEER]

Absolutely appreciate your visual explanations!!!

[@MichaelSambol]

thank you!

[@n.h.son1902]

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?

[@Zicrus]

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.

[@josecalles7634]

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

[@dannggg]

You always makes things clear

[@govindrai93]

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?

[@DannyJoseph]

It doesn't run n times it runs n-1 times so it should be n-1*logn

[@smoulibabca]

@@DannyJoseph n-1 = n in terms of algorithm complexity

[@劉梓堂]

Same though, I think that it's 0(n * log(n))

[@Zicrus]

​@@劉梓堂 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.

[@viper33m]

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

[@balive053]

Very clear explanation. Thanks very much!

[@Xxnightwalk1]

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

[@dannyelsupremo6127]

Amazing! Very straight to the point

[@govindrai93]

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!

[@NickWinters]

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

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

[@Zicrus]

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

[@01eksii]

Oh yeah, another addition to collection of golden clasics

[@WailingDarkness]

whats the purpose of l

[@user-jt4hk1rl8r]

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

[@teodorneagoe]

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)

[@Singh1405-l5u]

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

[@mfahmy6733]

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?

[@moriartyjames4856]

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.

[@aymanhww]

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

[@fedormiron1922]

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.

[@Zicrus]

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.

[@kuldeepchouhan8467]

It was very helpful. thanks!!

[@-_art0m_-632]

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?

[@nastrimarcello]

Because he's indexing from 1 instead of from zero.

[@DavidZapata-q4n]

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

[@MichaelSambol]

check my notes here: github.com/msambol/dsa/blob/master/data_structures/heap.py#L39

[@DavidZapata-q4n]

@@MichaelSambol Thanks, and great videos!

[@julianduhnen942]

Damn, this guy sounds like the Lord

[@colinburgess4316]

What do you do with the intersect of maxheap, and minheap, where there is a fuzziness between these two properties?

[@qiphoenix3043]

ur video is awesome!

[@Explainer400]

Why you start the array with 1

[@Eren-dm5xy]

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

[@Twst3628]

If your array starts with 0 left = 2i + 1 right = 2i + 2