Wriwitng pseudo code is easy once you understood the algorithm. Reading someone's pseudo code on the other hand can be quite annoying, because they may use different naming conventions, different syntax and even different "language" than you.
I guess Im randomly asking but does someone know of a method to get back into an Instagram account..? I somehow lost my password. I appreciate any tips you can give me!
I am genuinely impressed at how shit my professor is he takes 5 slides to explain this and never asks any of the many questions i had. This video did more for me than 2 lectures.
First i felt why u didnt explain how to build max heap but then it becomes clear as thats not the point of video and can be learnt seperately. You are making these look so simple. Thumbs up to you.
The best part is the very last portion where everything is summed up and pseudocode is given. Thanks! Exploring more videos to prepare for an interview!!
it manages O(n) by using a bottom-up approach. Each sub-tree in a heap must also maintain the heap property. When you run build-max-heap the runtime depends on the height of the tree. Since you can safely build a heap bottom-up, you would get something like this: O(n + (1/2)n + (1/4)n + (1/8)n + (1/16)n + ...), which simplifies to O(2n), or just O(n). That's not exactly what happens, but it's along those lines. You should google "linear time build heap" for more info.
i know this is a little late but thank you so much for this video!! the way you explained it, i understood this much better than when my prof talked about it in class. bonus points for the pseudocode at the end :D
Building a max heap does not guarantee that the heap array is sorted, it just means that the max heap property is maintained. This means that in the array, for every index i in the array, A[i] has children at A[2i] and A[2i + 1] with elements that are less than A[i]. However, nothing is stopping A[2i] from being greater than A[2i + 1] and vice versa. The build max heap did sort the array in descending order in the video, but that's just lucky. Now you might be wondering why is there no conditional to check if build max heap did get a lucky sort. While that would be effective in the cases where build max heap sorts the array (small number of cases), it brings down efficiency drastically for other cases, as you would have to check if the array is sorted (O(n) operation) for every heapify (n/2 heapify's), turning heap sort into a quadratic algorithm in the worst case
@@raphaelandrade555 Consider this: someone's native language is English and has lived in Japan for 2 years, and this person makes a video in Japanese, which incurs some native Japanese speaker saying "he's not saying proper/bad Japanese". It's like laughing at a 1-month-old not being able to walk.
hash sort by distribution function (for example linear) direct bin division placement, subsort each bin, O(n), divide and conquer, extended quick sort by multiple pivots at once, the bins
00:07 Heap sort is a sorting algorithm that uses the concept of a max-heap. 00:37 The video explains how to create a max heap from an unsorted array and uses heapify for faster performance. 00:53 Heap sort uses max heap to find the largest item and continuously creates max heaps. 01:15 Heap sort is based on representing an array as a tree 01:45 Heap sort involves building a max heap, swapping the largest item, and removing it from the tree. 02:12 Heapify moves the largest number to the top 02:39 Heap sort is a sorting algorithm 04:08 Heap sort has a time complexity of O(nlogn). Crafted by Merlin AI.
Brother please make a video on threaded binary tree insertion, your videos are great and in less time, great for revisions and understanding complex concepts easily and quickly ❤
I think the array you used in this example might be misleading, as when you do the max-heap you obtain a descendent sorted array and from there you can just flip it to get the sorted array.
@@AahanaHegde-py7ng max-heap just ensures that the parent node is greater than its children which doesn't guarantee that the tree written in the array form will be sorted in descending order. For example, when the original array has max-heap applied to it in the video it returns the array 9 8 5 3 2 1 (which is sorted descending). However, if you look at the representation of the tree in the video and imagine flipping the left sub tree with the right you would get the array 9 5 8 1 3 2. This still satisfies the condition that the parent node is greater than the child, but the array is no longer sorted.
1:38 and we are done, just call reverse on the array.... wait why are you messing it up again? I think the example data made this more confusing as it ended up sorted after the first build-max-heap call.
I'm very confused about something. When you call build-map-heap, you are sorting the entire array in descending order. At that point, the array is sorted. Why would you keep sorting after that point?
for example, left child can be less than right one, so now array is unsorted UPD: the left child of right child can be greater than the right child of left child. This try must be correct :)
Yes it's sorted but remember that it is *heap-ordered* and the resulting array is in the binary tree notation. The last portion of the algorithm is still necessary to have a sorted array by making use of the heap ordered array by continuously removing the largest element and reheapfying until you get your sorted array
@@azzam7239 I don't really understand, in all the examples I see, the heap is physically stored as an array, and max heapify sorts that array perfectly, so why don't we just use that array?
1:35 At first function call of "Build Max Heap" we have sorted array in descending order, we fix this simply by swapping. Why are we performing these many operations ? Anyone please !
I'm confused. Why do you need two functions for this? In both cases the input was a tree and the output was a max heap. Maybe it's because we know that after the first one it's only the root node that is out of place, and we use another function that doesn't do unnecessary calculations related to other nodes. Then it'd be better if the name was more descriptive. Considering how it doesn't operate on the whole tree, it can be named something like heapify_branch instead
Could you take a look at the full playlist, I think it will help: th-cam.com/play/PL9xmBV_5YoZNsyqgPW-DNwUeT8F8uhWc6.html. Code: github.com/msambol/dsa/blob/master/sort/heap_sort.py
Lokesh Joshi it was a coincidence that his max heap was already sorted in descending order. That will not always be the case. Should be a different example to avoid confusion like this
Thank you for the reply. But in this case for BuildMaxHeap() we call Heapify() n/2 times and each time costs O(logn) time, so the total time complexity is O(nlogn). Is there anything not proper?
魏雍 incorrect because the heapify for nodes at height h-1 only trickle down once, the ones above it trickle down twice, and so on. So for each level, the amount of work goes down as you go deeper into levels. Not each one of the n/2 nodes will do logn work! in fact the only one that will do logn work is the root node :) I suggest you have a look at CLRS. It shows the correct way of computing this tighter bound.
I wonder if on average, plucking the 2 largest elements from the maxheap (if available), will speed things up. It seems wasteful to not pluck 2 at a time since we know the 2nd one will be one of the roots children. I traced this example on paper and it seems to work well. However I would like to know on say a 1 million entry tree (19 levels deep), how much faster it would be in real time. I would want to randomly generate 1 million numbers, store them for input to both "flavors" of heapsort, then make a table of outcomes. For example, 4.7 seconds classic heapsort, 4.6 seconds modified heapsort. I would also want to try cases with 1 million unique numbers, cases with 1 million small numbers with lots of repeats (like in the range 1 to 1000), and 1 million numbers with large gaps (like use 1 million random 32 bit numbers). I think the results would be interesting. Maybe someone can try it and report back.
So, when you do max heap the first time, you get a sorted array but in a different direction. Can't you just make a new array that has the same values, but reversed and you are finished with the sorting?
@@kylestormeyes4976 Actually, It is not correct. It only happens in certain cases, and this one is one of them. I should've deleted the comment when I realised that.
What's the point of heap-sorting when we already have a sorted max-heap at 1:40? Yes, it's sorted backwards, but heapsorting takes more time than reversing a sorted array. I don't really get it. EDIT: I got it and I think the example used in the video wasn't that good, because a max-heap doesn't necessarily end up being a sorted array.
Everybody gangsta till pseudocode kicks in
fr😂
True lol
Wriwitng pseudo code is easy once you understood the algorithm. Reading someone's pseudo code on the other hand can be quite annoying, because they may use different naming conventions, different syntax and even different "language" than you.
I guess Im randomly asking but does someone know of a method to get back into an Instagram account..?
I somehow lost my password. I appreciate any tips you can give me!
@Marley Alexzander Instablaster ;)
Audio is so clear, amazingly static free( it is so near to being a meditation app audio).
*listens to heap sort as meditation*
Lol
I am genuinely impressed at how shit my professor is he takes 5 slides to explain this and never asks any of the many questions i had. This video did more for me than 2 lectures.
my lecture explained it over 7 slides, kind of understandable, but the video sure helped
First i felt why u didnt explain how to build max heap but then it becomes clear as thats not the point of video and can be learnt seperately. You are making these look so simple. Thumbs up to you.
you just saved my semester. I have been binging your channel
This was very clear to me. Now I understand heap sort in a visual sense thank you
What a clear explanation. I couldn't understand what teacher said till I see this video 👍
I like the small time of these videos. Neat graphics. Good work.
What a nice explanation! That made my understanding of the algorithm a lot easier, thanks a lot
The best part is the very last portion where everything is summed up and pseudocode is given. Thanks! Exploring more videos to prepare for an interview!!
how'd the interview go
I owe my entire CS degree to videos like this. Explains stuff much better than professors you have to pay for : ^)
when you IPO your tech company you can toss me 1% ;)
ok, better than my lecture just read through slides
i agree
Until you are asked to prove the time complexity ^^
Great tomorrow our mem will be taken our class test..now i watching your video😊great.. ❤
This process was very confusing in my lecture but looking at it with the array and the tree side-by-side made it crystal clear what was going on.
You skipped all the details on how build-max-heap works! That was the part I wanted to see, I need to understand how it manages complexity of O(n)
Me too..stupid video
it manages O(n) by using a bottom-up approach. Each sub-tree in a heap must also maintain the heap property. When you run build-max-heap the runtime depends on the height of the tree. Since you can safely build a heap bottom-up, you would get something like this: O(n + (1/2)n + (1/4)n + (1/8)n + (1/16)n + ...), which simplifies to O(2n), or just O(n). That's not exactly what happens, but it's along those lines. You should google "linear time build heap" for more info.
Saved lots of time thanks yt algorithm for finding the best and fastest way of finding this video ❤
after watching several videos, I find it the best
i know this is a little late but thank you so much for this video!!
the way you explained it, i understood this much better than when my prof talked about it in class.
bonus points for the pseudocode at the end :D
omg my textbook made this so confusing, but this gave me so much clarity thank you so much!
Doesn't make sense, if the build max heap has already sorted in desc, why would I need to do another sort again.
that's what I thought, it doesn't make any sense
Building a max heap does not guarantee that the heap array is sorted, it just means that the max heap property is maintained. This means that in the array, for every index i in the array, A[i] has children at A[2i] and A[2i + 1] with elements that are less than A[i]. However, nothing is stopping A[2i] from being greater than A[2i + 1] and vice versa.
The build max heap did sort the array in descending order in the video, but that's just lucky. Now you might be wondering why is there no conditional to check if build max heap did get a lucky sort. While that would be effective in the cases where build max heap sorts the array (small number of cases), it brings down efficiency drastically for other cases, as you would have to check if the array is sorted (O(n) operation) for every heapify (n/2 heapify's), turning heap sort into a quadratic algorithm in the worst case
Thank you for speaking proper English.
LMFAOOOOOO [TRUUUUUUUUUUUUU]
LOL
Thats fucking racist tho
@@dreamy6517 That's not racist, there are people who speak bad english, what's the problem with that?
@@raphaelandrade555 Consider this: someone's native language is English and has lived in Japan for 2 years, and this person makes a video in Japanese, which incurs some native Japanese speaker saying "he's not saying proper/bad Japanese". It's like laughing at a 1-month-old not being able to walk.
damn i totally lost until i found your video. Thanks for sharing, it actually helped me a lots
My professor didn't even post a class, she just uploaded links to all your sort videos instead.
Quite shitty tho
Well unless she wanted to explain harder topics
hash sort by distribution function (for example linear) direct bin division placement, subsort each bin, O(n), divide and conquer, extended quick sort by multiple pivots at once, the bins
Always appreciate CS tutorials without the Hindi accent 👍🏿
gonna share this channel w/ all my CS friends omg
Well congrats on y’all’s graduation
@@masterjif9506 😂
Great explanation. Short and precious.
This saved me for my algorithms test. Thank you
Nice video, Michael. This is very clearly explained.
best explanation on how it works
I turned it into "heap sort in 2 minutes"
I'm so happy 30% was passing in my DSA course...
Most amazing and simplified explanation
Heap sort in 4 mins!? 😱 You desperately need code optimization 😂 just kidding. Great video, well well explained. thanks ✌️👏
00:07 Heap sort is a sorting algorithm that uses the concept of a max-heap.
00:37 The video explains how to create a max heap from an unsorted array and uses heapify for faster performance.
00:53 Heap sort uses max heap to find the largest item and continuously creates max heaps.
01:15 Heap sort is based on representing an array as a tree
01:45 Heap sort involves building a max heap, swapping the largest item, and removing it from the tree.
02:12 Heapify moves the largest number to the top
02:39 Heap sort is a sorting algorithm
04:08 Heap sort has a time complexity of O(nlogn).
Crafted by Merlin AI.
Short and sweet explanation. Thank you:)
Dude, your short explanation is awesome
From 2020 that’s still bright video 👩💻
saving lives to this day, thank you very much
Yes, yes, yes. This is insanely good. Thanks for the video
Awesome video, way better than my professor!
Not all heroes wear capes. You saved me😮💨
💪🏼❤️
Thanks for everything you're doing buddy
Brother please make a video on threaded binary tree insertion, your videos are great and in less time, great for revisions and understanding complex concepts easily and quickly ❤
I think the array you used in this example might be misleading, as when you do the max-heap you obtain a descendent sorted array and from there you can just flip it to get the sorted array.
yes this is what is confusing me, im new to programming, but can you explain why just using max heap isnt enough?
@@AahanaHegde-py7ng max-heap just ensures that the parent node is greater than its children which doesn't guarantee that the tree written in the array form will be sorted in descending order. For example, when the original array has max-heap applied to it in the video it returns the array 9 8 5 3 2 1 (which is sorted descending). However, if you look at the representation of the tree in the video and imagine flipping the left sub tree with the right you would get the array 9 5 8 1 3 2. This still satisfies the condition that the parent node is greater than the child, but the array is no longer sorted.
Your videos are incredible, very useful - thanks!
after 5 videos explaining Heap Sort I get it now, next binary tree...God help me.
Kind of weird to understand a heap sort without understand what a binary tree is
@@boggeshzahim3713 I said the same thing lol
A binary tree is just a tree in which each node has 2 children at most, just a definition.
Hmm, not sure I'm going to retain this long enough to get these test questions right lol
Excellent explanation, simple and clear!
Thank you sir. Just simple to understand ☺️
great tutorial! took me a while to understand but now i get it thank you for teaching me this
The best tutorial of heap sort :)
I have mid term comming up, thanks sir
You deserves a new subscriber bruh!!
1:38 and we are done, just call reverse on the array.... wait why are you messing it up again? I think the example data made this more confusing as it ended up sorted after the first build-max-heap call.
That is the point
Noice...much better video than others
Well explained sir, very nice explanation.
This is the Ffff reason I subscribed
Good as always! Thank you Michael!
Very clearly explained. Thank you sir.
Thank you for this sample of heap sort!!! 😍
I'm very confused about something. When you call build-map-heap, you are sorting the entire array in descending order. At that point, the array is sorted. Why would you keep sorting after that point?
for example, left child can be less than right one, so now array is unsorted
UPD: the left child of right child can be greater than the right child of left child. This try must be correct :)
Yes it's sorted but remember that it is *heap-ordered* and the resulting array is in the binary tree notation. The last portion of the algorithm is still necessary to have a sorted array by making use of the heap ordered array by continuously removing the largest element and reheapfying until you get your sorted array
@@azzam7239 I don't really understand, in all the examples I see, the heap is physically stored as an array, and max heapify sorts that array perfectly, so why don't we just use that array?
Great Explanation..Keep it up buddy
A very nice explanation. Thanks
1:35 At first function call of "Build Max Heap" we have sorted array in descending order, we fix this simply by swapping. Why are we performing these many operations ?
Anyone please !
that just happens for this example.. doesn't happen always
Tq sir less time more information about heap sort
Very nice explanation!! Thanks a lot. 😊
I don't get it, build max heap sorts the tree, right?
Why not just build the array with the sorted tree backwards, linearly?
In the example, I failed to see the difference in functionality between heapify and max heap :/ Good vid though, keep it up!
Think of heapify as a way to restore the max heap property "Max element at root" when we remove the root
I'm confused. Why do you need two functions for this? In both cases the input was a tree and the output was a max heap.
Maybe it's because we know that after the first one it's only the root node that is out of place, and we use another function that doesn't do unnecessary calculations related to other nodes. Then it'd be better if the name was more descriptive. Considering how it doesn't operate on the whole tree, it can be named something like heapify_branch instead
Could you take a look at the full playlist, I think it will help: th-cam.com/play/PL9xmBV_5YoZNsyqgPW-DNwUeT8F8uhWc6.html.
Code: github.com/msambol/dsa/blob/master/sort/heap_sort.py
so clearly explained! Wow thank you
greatly simplified. Superb explanation :)
at 1:35 why you are sorting the sorted array
Lokesh Joshi it was a coincidence that his max heap was already sorted in descending order. That will not always be the case. Should be a different example to avoid confusion like this
After you buildMaxHeap the array was sorted already in inverse way. Why don't you just reverse it?
Just a little mistake, BuildMaxHeap() consumes O(nlogn) time.
(Above upper bound is not tight enough, BuildMaxHeap() operation costs linear time)
Not really. It's O(n) because the work at the bottom-most level is unneeded, so you effectively only work on half of the nodes. Check CLRS!
Thank you for the reply. But in this case for BuildMaxHeap() we call Heapify() n/2 times and each time costs O(logn) time, so the total time complexity is O(nlogn). Is there anything not proper?
魏雍 incorrect because the heapify for nodes at height h-1 only trickle down once, the ones above it trickle down twice, and so on. So for each level, the amount of work goes down as you go deeper into levels. Not each one of the n/2 nodes will do logn work! in fact the only one that will do logn work is the root node :)
I suggest you have a look at CLRS. It shows the correct way of computing this tighter bound.
Checked CLRS, it's my misunderstanding(^_^). You are right Slash!
魏雍 cheers! :)
I wonder if on average, plucking the 2 largest elements from the maxheap (if available), will speed things up. It seems wasteful to not pluck 2 at a time since we know the 2nd one will be one of the roots children. I traced this example on paper and it seems to work well. However I would like to know on say a 1 million entry tree (19 levels deep), how much faster it would be in real time. I would want to randomly generate 1 million numbers, store them for input to both "flavors" of heapsort, then make a table of outcomes. For example, 4.7 seconds classic heapsort, 4.6 seconds modified heapsort. I would also want to try cases with 1 million unique numbers, cases with 1 million small numbers with lots of repeats (like in the range 1 to 1000), and 1 million numbers with large gaps (like use 1 million random 32 bit numbers). I think the results would be interesting. Maybe someone can try it and report back.
Amazing quality. Dark mode option perhaps?
thank you! all new videos for sure. I wish there was an easy option for dark mode on old videos, but it'd require remaking them.
Thanks a lot, Love from INDIA
Just having a chicken curry! Sending love to INDIA 🇮🇳 and all the boys who helped me with my university degree 😆
When you learnt Binary tree search and now eager to use it in this heap sort knowing it's not gonna be that smooth, bruh.
simple and effective, thanks for the video
Clear explanation. Thanks.
Awesome explanation
thank you!
So, when you do max heap the first time, you get a sorted array but in a different direction. Can't you just make a new array that has the same values, but reversed and you are finished with the sorting?
yahh like put everything into a stack and then take it out in order ?? I thought the same :P hopefully someone will answer
@@kylestormeyes4976 Actually, It is not correct. It only happens in certain cases, and this one is one of them. I should've deleted the comment when I realised that.
@@maya.n Thank you for not deleting the comment. I thought the same thing.
The best tutorial. Thank you
Very informative. Thanks a lot
Very nice explanation. Just subscribed.
What's the point of heap-sorting when we already have a sorted max-heap at 1:40? Yes, it's sorted backwards, but heapsorting takes more time than reversing a sorted array. I don't really get it.
EDIT: I got it and I think the example used in the video wasn't that good, because a max-heap doesn't necessarily end up being a sorted array.
Very good explanation. Thanks
awesome, very much appreciated!
Amazing and concise. Thanks
From the Pseudo code, as the for loop in the HeapSort() is already decrementing from n to 1, the (n - 1) in the HeapSort() should be useless?
It's that easy? , man prof took too long to teach us this simple thing
great video!
is this applicable in python?
github.com/msambol/dsa/blob/master/sort/heap_sort.py
You haven't pass the n as a parameter in the heapify method.
Videos are awesome man.
thank you
Someone saw how we got from a tree to a max heap? It was skipped!
good job Michael!
lol 3 hours of lecture and you explain in 4mins
thank so much , liked and subscribed i have test and this helped me a lot ^^