Adrian Lundberg Well that's a dang shame. Thanks for the correction. I will fix it in annotations, but might not repost it, as that erases UA-cam's ranking for the video.
Algorithms with Attitude Haha well, don't worry, it's such an obvious typo. I just wanted to point it out in case you were going to reeuse the slides some time in the future
It's just a bit frustrating, because if enough people watch the video, I am sure that some will be just on the border between understanding it and not understanding it, and a minor mistake might push them to the wrong side. I need a proofreader. Anyway, I will annotate it.
Your tutorials are really among the best I've ever seen. The beautiful animated graphics make it feels easy enough to be comprehended by self-learners, yet the content is really deep and abstract. Many thanks!
+Filip Kopecký I put a good amount of time into these videos to try to make them concise but still intuitive and fairly detailed, in hopes of making it easier for others. Good to know it is working for some of you. Please spread the word...
Thank you for making these! I'm a CS graduate and after spending enough years using tools that other people have made, it's sometimes nice to go grab a reminder without a 60 minute lecture (turns out application development doesn't involve building heaps from scratch too often). Anyways, if you decided to run on Patreon or somesuch, I'll happily subscribe :)
I hope my students don't get the impression that they will be building every data structure from scratch... No plans for any Patreon account right now. If people paid, they might actually have some standards...
I am not exactly sure what this refers to, unless maybe its a reference to the 70s look I have going on. But, I do occasionally enjoy me some cheesy 70s music.
Please keep making It was one worth of a watch. Though the mathematics was good for understanding, I just tried out this algorithm and I believe I can use it in my code. Thanks again
In the previous video, didn't the iterated insertion take the least number of operations when the number was small? Because in that case, wouldn't the root take the most operations in both insertion and linear heap building?
Insertion takes no more than logarithmic in the size of the heap, but if you grow a heap by iterated insertion, the last n/2 insertions are all into a heap of size n/2 or larger, and log (n/2) = (log n) - 1. If you insert the first number in the array first, it becomes the root of the newly formed heap of size 1. The last value inserted goes into a leaf position, and then can work its way up by heapify. There is only 1 heap. For linear time build heap, you start with a whole bunch (n/2) of small heaps of size 1 each, and then add new roots to merge 2 heaps. Most all merges are of small heaps. The last insertion merges two heaps of size almost n/2 each, and it can take logarithmic time, but the vast majority of merges are between tiny heaps, and in total, it takes worst case linear time.
+Alexander Kuptsov The slides are pdf files written with latex. The graphics are javascript with svg. I film in front of a green cloth. I am using Camtasia to put it together into a movie.
+Algorithms with Attitude Hm, I thought so, I was just doubtful whether one could get such slides with a combination of all that. I'm a hobbyist, but I will post on a Coursera forum where I'm taking CS courses currently. Thanks again for your amazing work!
+Alexander Kuptsov Editing is... non trivial. This heap series is the first one I did, I think the more recent ones (starting December 2015) look a bit better, and I'm no longer looking off so much to the side. Which Coursera course? I feel like my videos are pretty different than others out there, but am obviously not in an unbiased position to judge. If you have time, let me know strengths/weaknesses against their videos.
Great video, thank you! Sometimes it can be hard to find its subsequent videos, would you consider putting down the links of subsequent videos in description?
This was the first series I put up. For later ones, I just give a link to the playlist using annotations (which don't work on mobile), and for even later ones, I start using "cards" (which do). A link to the playlist in the description sounds totally reasonable, I will add that at some point. For this video, I switched over to cards and the new end-screen stuff, after reading your comment, but I will do that more systematically some time in the future, when time permits. Thanks for the suggestion.
+Maxime Perusse It was a joke that references ua-cam.com/video/MiyLo8adrWw/v-deo.html by pretending the remove of earwax requires an algrothim in the same way the remove of a node from a heap requires one.
In this video it looks like you are doing siftUp starting from the very last element of the array. From this link, (stackoverflow.com/questions/13025163/why-siftdown-is-better-than-siftup-in-heapify), they say that siftDown is faster. Can you please clarify this situation?
For the first minute of the video, the animation shows how to build a heap by iterated insertion. Insertion uses the siftUp operation, and in the analysis of that approach (around the 0:30 mark), I mention that it has worst-case O(n lg n) runtime, though with random values, it has O(n) expected time. Next, starting at 1:09 in the video, the rest of the video uses the siftDown approach: instead of starting with the first element and growing it as a tiny heap, start with the last n/2 elements, and take each to be the root of a 1 value heap. Then, working from the middle of the array back, for each value, take it to be the root of a new heap, and sift that root down as needed. Because most elements start near the bottom, the sum of time needed for sifting elements down is O(n) worst case. The proof of that which I give at the end of the algorithm is pretty slick, and I haven't seen that argument used in the heap context before, though it may be out there somewhere. Thanks for the question. In watching the transition from one approach to the other, I now see that of course my explanation isn't quite as crystal clear as I had thought. Hopefully this explanation will help (though depending on what source you use, siftUp and siftDown might be known by other names).
Thank you very much for the explanation. In my previous think, siftUp and siftDown meant starting at the the bottom and top respectively, where we check that the heap invariant holds. I see now that we are really running siftDown on every subtree going from the end of the array (or really the middle of the array because the leafs have no children) and calling siftDown until we reach the root. Thanks for all these great videos :)
+PRANJALI PAI I plan to get to them, but it won't be for a long time. I have some future topics at ua-cam.com/video/qg1o90S6aCw/v-deo.html but they will take a long time to get to. In the meantime, my previous channel (under David Taylor) had some somewhat lower quality videos on BTrees. Watch that playlist through the section on 234 trees, which are very closely related to red black trees. It is a different way of looking at it, but can help your intuition for red black trees. (After you watch that video, I can post a comment explaining how the two trees are related.)
+PRANJALI PAI Just to clarify, red black trees and 234trees are implemented quite differently. But it turns out that the tree structure of red black trees ends up looking like a 234 tree if you consider a black node, and any of its red children, all together. Combined, they look very much like a logical 234 node. But, the coding is really different. Rather than tracking rotations, I thought the 23 and 234 trees were more intuitive, so I taught them instead. Plus, they generalize nicely to BTrees. That is why I made that playlist.
Algorithms with Attitude Ok Thank you !!:) I ll go through Red Black trees. I m done watching the videos in you playlist:) They are very helpful and easy to understand!:)
Hi David, thanks a lot. These are great set of videos. Could you number the videos, so that a learning trail is easier? For example binary heap lectures, it was difficult to find the next lecture. Numbering could help a lot.
SOS If you are watching with annotations turned on, the end of one video will generally have a link to the next one. Also, there are playlists: for heaps, you can check out ua-cam.com/play/PLSVu1-lON6Lwqj5nDqg8YyD7f4tjLMMBN.html For some sets, the playlist won't be quite linear. On one of the analysis playlists, there is a sequence of 3, and a 4th video that can be watched anytime after the first one of that playlist. Using the annotation links, you can probably take more than one path through, but the playlist should always have a reasonable path through the videos. Notice, for the heap playlist, the last video in the playlist is very much optional. You could watch it 2nd, or skip it. Because it is more advanced, but also less important, I put it last in the playlist. Hope this helps.
Excellent Job! Thank you for these. Also noticed the 2^n vs 1/2^n typo as mentioned by Adrian Lunberg and saw the comment. Not familiar with UA-cam comments, can you pin comments so they stay near or at the top?
Here is what it might look like: a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] for i in range(len(a) // 2, -1, -1): parent = i while True: candidates = [parent, 2 * parent + 1, 2 * parent + 2] candidates = [e for e in candidates if e < len(a)] largest = max(candidates, key=lambda e: a[e]) if largest == parent: break else: a[parent], a[largest], parent = a[largest], a[parent], largest
I'm read about binary heaps in Cormen book, but there is nothing about Union operation. At first i think thecond heaps elements must sequentially insert in the first heap, but this is not effective, then i watch your video. I want to read about this algorithm from books or other oficial source. So if you know about this-can you say the name of book and the chapter-Thank You
+liljan777 If you are using the 3rd edition (probably the 2nd edition too) Cormen, it is Section 6.3. They call it BUILD-MAX_HEAP, and it directly makes use of Section 6.2, MAX-HEAPIFY. Note, their text may use different language than I use, but Max-Heapify assumes that you have, overall, a heap shape, and that the left and right children of the root are roots of valid subheaps. It then corrects the root. I don't remember how different my presentation is from theirs (a year later, details escape me), but I try to make a presentation that I think is intuitive. It should complement the book, but it won't follow their exact presentation.
This is the second comment on this video making that comparison. Even if you mean the alcoholic version that was on his last legs in Logan, I'll take it.
I am an angry man. More seriously, in trying to speak quickly but clearly, it came out that way much more than intended. I don't exactly have an actual studio with nice acoustics or anything.
Thank you very much! However, I would like to point out a typo at 4:50. It should say 1/2^h, otherwise it would sum up to n * infinity, not n *unity.
Adrian Lundberg Well that's a dang shame. Thanks for the correction. I will fix it in annotations, but might not repost it, as that erases UA-cam's ranking for the video.
Algorithms with Attitude Haha well, don't worry, it's such an obvious typo. I just wanted to point it out in case you were going to reeuse the slides some time in the future
It's just a bit frustrating, because if enough people watch the video, I am sure that some will be just on the border between understanding it and not understanding it, and a minor mistake might push them to the wrong side. I need a proofreader. Anyway, I will annotate it.
Can't even annotate it without eliminating the end screen stuff. Maybe people will just see your comment...
Algorithms with Attitude
Pin his comment to make sure people see it
These videos are making me learn algorithms at worst case linear time, instead of n^2 from textbooks!
😂😂 nice one
Your tutorials are really among the best I've ever seen. The beautiful animated graphics make it feels easy enough to be comprehended by self-learners, yet the content is really deep and abstract. Many thanks!
I went from having no idea to understanding how it works and why it works in about 5 minutes, this is a great video.
+Filip Kopecký I put a good amount of time into these videos to try to make them concise but still intuitive and fairly detailed, in hopes of making it easier for others. Good to know it is working for some of you. Please spread the word...
You are the best at explaining algorithms I have seen. Well done!
The animation is great. Helped me to quickly grasp the working of the algorithm.
this video is dope! Literally best explanation I've ever seen
I love this channel.. Precise explanations.. Thanks for your good work!!
Thank you for making these! I'm a CS graduate and after spending enough years using tools that other people have made, it's sometimes nice to go grab a reminder without a 60 minute lecture (turns out application development doesn't involve building heaps from scratch too often).
Anyways, if you decided to run on Patreon or somesuch, I'll happily subscribe :)
I hope my students don't get the impression that they will be building every data structure from scratch...
No plans for any Patreon account right now. If people paid, they might actually have some standards...
Great work, Thank you ! Looking forward for more videos, Please keep making such awesome videos !
Thanks. Please subscribe, and tell classmates if you are taking a related course.
+Algorithms with Attitude Done :)
I love this channel. Keep up the good work!
I'm trying, but it is difficult, as I have no video making skills, and am quite lazy. Besides that part, I am trying.
I appreciate the effort anyway!
OMG. Clear and precise animations! Thanks
+Lawrence Dizon Thanks, I am doing my best to make the "fact transfer" part of the material easy.
listening to cheesy 70s music and nights are better now that i found you came on.
I am not exactly sure what this refers to, unless maybe its a reference to the 70s look I have going on. But, I do occasionally enjoy me some cheesy 70s music.
Really an awesome channel! Just don;t stop making more interesting videos :D
Nice! Great visual explanation
Awesome videos , proper explanation , thanks a lot !
Please keep making
It was one worth of a watch. Though the mathematics was good for understanding, I just tried out this algorithm and I believe I can use it in my code. Thanks again
Love your explaining style! +1
Briefly and very clear
Absolute Legend.
Thank you for inspiring me!
In the previous video, didn't the iterated insertion take the least number of operations when the number was small? Because in that case, wouldn't the root take the most operations in both insertion and linear heap building?
Insertion takes no more than logarithmic in the size of the heap, but if you grow a heap by iterated insertion, the last n/2 insertions are all into a heap of size n/2 or larger, and log (n/2) = (log n) - 1. If you insert the first number in the array first, it becomes the root of the newly formed heap of size 1. The last value inserted goes into a leaf position, and then can work its way up by heapify. There is only 1 heap.
For linear time build heap, you start with a whole bunch (n/2) of small heaps of size 1 each, and then add new roots to merge 2 heaps. Most all merges are of small heaps. The last insertion merges two heaps of size almost n/2 each, and it can take logarithmic time, but the vast majority of merges are between tiny heaps, and in total, it takes worst case linear time.
Dear Sir,
What you do is absolutely top notch! Thanks a million!
May I ask you what software you use to do such beautifully designed videos?
+Alexander Kuptsov
The slides are pdf files written with latex.
The graphics are javascript with svg.
I film in front of a green cloth.
I am using Camtasia to put it together into a movie.
+Alexander Kuptsov Thanks. Please let classmates know.
+Algorithms with Attitude Hm, I thought so, I was just doubtful whether one could get such slides with a combination of all that.
I'm a hobbyist, but I will post on a Coursera forum where I'm taking CS courses currently.
Thanks again for your amazing work!
+Alexander Kuptsov Editing is... non trivial. This heap series is the first one I did, I think the more recent ones (starting December 2015) look a bit better, and I'm no longer looking off so much to the side.
Which Coursera course? I feel like my videos are pretty different than others out there, but am obviously not in an unbiased position to judge. If you have time, let me know strengths/weaknesses against their videos.
Great video, thank you! Sometimes it can be hard to find its subsequent videos, would you consider putting down the links of subsequent videos in description?
This was the first series I put up. For later ones, I just give a link to the playlist using annotations (which don't work on mobile), and for even later ones, I start using "cards" (which do). A link to the playlist in the description sounds totally reasonable, I will add that at some point. For this video, I switched over to cards and the new end-screen stuff, after reading your comment, but I will do that more systematically some time in the future, when time permits. Thanks for the suggestion.
Hey, first year of CS & math first degree here.
What method do you use for removal of ear wax?
L I drip some meat sauce in my ear and let my dog have at it.
Algorithms with Attitude Lovely! I'll try this with my cat. Many thanks.
+L what the hell is going on here
+Maxime Perusse It was a joke that references ua-cam.com/video/MiyLo8adrWw/v-deo.html by pretending the remove of earwax requires an algrothim in the same way the remove of a node from a heap requires one.
In this video it looks like you are doing siftUp starting from the very last element of the array. From this link, (stackoverflow.com/questions/13025163/why-siftdown-is-better-than-siftup-in-heapify), they say that siftDown is faster. Can you please clarify this situation?
For the first minute of the video, the animation shows how to build a heap by iterated insertion. Insertion uses the siftUp operation, and in the analysis of that approach (around the 0:30 mark), I mention that it has worst-case O(n lg n) runtime, though with random values, it has O(n) expected time.
Next, starting at 1:09 in the video, the rest of the video uses the siftDown approach: instead of starting with the first element and growing it as a tiny heap, start with the last n/2 elements, and take each to be the root of a 1 value heap. Then, working from the middle of the array back, for each value, take it to be the root of a new heap, and sift that root down as needed. Because most elements start near the bottom, the sum of time needed for sifting elements down is O(n) worst case. The proof of that which I give at the end of the algorithm is pretty slick, and I haven't seen that argument used in the heap context before, though it may be out there somewhere.
Thanks for the question. In watching the transition from one approach to the other, I now see that of course my explanation isn't quite as crystal clear as I had thought. Hopefully this explanation will help (though depending on what source you use, siftUp and siftDown might be known by other names).
Thank you very much for the explanation. In my previous think, siftUp and siftDown meant starting at the the bottom and top respectively, where we check that the heap invariant holds. I see now that we are really running siftDown on every subtree going from the end of the array (or really the middle of the array because the leafs have no children) and calling siftDown until we reach the root.
Thanks for all these great videos :)
Please do Red black trees as well!!!
Understood the concept s soo well!!
+PRANJALI PAI I plan to get to them, but it won't be for a long time. I have some future topics at ua-cam.com/video/qg1o90S6aCw/v-deo.html but they will take a long time to get to. In the meantime, my previous channel (under David Taylor) had some somewhat lower quality videos on BTrees. Watch that playlist through the section on 234 trees, which are very closely related to red black trees. It is a different way of looking at it, but can help your intuition for red black trees. (After you watch that video, I can post a comment explaining how the two trees are related.)
Algorithms with Attitude Ok Thank you soo much, Ill just go through the videos and comment back!:)
+PRANJALI PAI Just to clarify, red black trees and 234trees are implemented quite differently. But it turns out that the tree structure of red black trees ends up looking like a 234 tree if you consider a black node, and any of its red children, all together. Combined, they look very much like a logical 234 node. But, the coding is really different. Rather than tracking rotations, I thought the 23 and 234 trees were more intuitive, so I taught them instead. Plus, they generalize nicely to BTrees. That is why I made that playlist.
Algorithms with Attitude Ok Thank you !!:)
I ll go through Red Black trees. I m done watching the videos in you playlist:) They are very helpful and easy to understand!:)
hope you will be back uploading videos.
Well explained
Hi David, thanks a lot. These are great set of videos. Could you number the videos, so that a learning trail is easier? For example binary heap lectures, it was difficult to find the next lecture. Numbering could help a lot.
SOS If you are watching with annotations turned on, the end of one video will generally have a link to the next one. Also, there are playlists: for heaps, you can check out ua-cam.com/play/PLSVu1-lON6Lwqj5nDqg8YyD7f4tjLMMBN.html
For some sets, the playlist won't be quite linear. On one of the analysis playlists, there is a sequence of 3, and a 4th video that can be watched anytime after the first one of that playlist. Using the annotation links, you can probably take more than one path through, but the playlist should always have a reasonable path through the videos.
Notice, for the heap playlist, the last video in the playlist is very much optional. You could watch it 2nd, or skip it. Because it is more advanced, but also less important, I put it last in the playlist.
Hope this helps.
I wish you were my Data structures professor
Excellent Job! Thank you for these. Also noticed the 2^n vs 1/2^n typo as mentioned by Adrian Lunberg and saw the comment. Not familiar with UA-cam comments, can you pin comments so they stay near or at the top?
Perhaps if lots of people upvote his comment? I don't see a way from my end.
Thank you!
Here is what it might look like:
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
for i in range(len(a) // 2, -1, -1):
parent = i
while True:
candidates = [parent, 2 * parent + 1, 2 * parent + 2]
candidates = [e for e in candidates if e < len(a)]
largest = max(candidates, key=lambda e: a[e])
if largest == parent:
break
else:
a[parent], a[largest], parent = a[largest], a[parent], largest
Hello. Can you say the source of this algorithm ?Where i can read about this algorithm?
+liljan777 Cormen et al. Introduction to Algorithms, among many textbooks. The algorithm is pretty old.
+Algorithms with Attitude The Cormen book is obviously not the original source, but is widely available.
I'm read about binary heaps in Cormen book, but there is nothing about Union operation. At first i think thecond heaps elements must sequentially insert in the first heap, but this is not effective, then i watch your video. I want to read about this algorithm from books or other oficial source. So if you know about this-can you say the name of book and the chapter-Thank You
+liljan777 If you are using the 3rd edition (probably the 2nd edition too) Cormen, it is Section 6.3. They call it BUILD-MAX_HEAP, and it directly makes use of Section 6.2, MAX-HEAPIFY. Note, their text may use different language than I use, but Max-Heapify assumes that you have, overall, a heap shape, and that the left and right children of the root are roots of valid subheaps. It then corrects the root.
I don't remember how different my presentation is from theirs (a year later, details escape me), but I try to make a presentation that I think is intuitive. It should complement the book, but it won't follow their exact presentation.
Thank you very match! Your video is very help me
Damn, didn't know Logan retired from the X-Men to teach CS algorithms
This is the second comment on this video making that comparison. Even if you mean the alcoholic version that was on his last legs in Logan, I'll take it.
Hello from Georgia Tech
Good luck with the test 2 on Wesnesday CS1332 Kidos
I get this sense you are semi shouting into the microphone.
I am an angry man.
More seriously, in trying to speak quickly but clearly, it came out that way much more than intended. I don't exactly have an actual studio with nice acoustics or anything.
wolverine teaching data structures.
If you look in the background, the evidence is there... ua-cam.com/video/p2sKmIaNAbw/v-deo.html
oh god, he grew a beard.
San jose state University!! YAY
Cool
aren't you the best :)
Uhhhmmm... yes? I am? So you should definitely subscribe and tell all your friends?
Excuse me sir you have a heap on your face
I wish someone had told me earlier, I walked around half the day with that thing on.
Nerdy Hugh Jackman... is that you?
I will definitely take that.
Really an awesome channel! Just don;t stop making more interesting videos :D