One of the best video series on the topic. I call it an art to be able to explain complex concepts and definitions with ease and and add a pinch of humor as well. David this is awesome!!
This channel really is algorithms with attitude! You keep me awake with all those not-so-subtle jokes. But besides that thank you so much, you've really helped me in not only catching up in my data structures class, but also in getting ahead! Thank you!
+Brandon Bryant Thank you, though I suspect I wouldn't be hired so easily: it is pretty hard to get a professorship, each of your professors was probably chosen out of 100+ applicants. Crazy, right? Hopefully that will insulate their egos should one of them see this comment (or you could delete it). Mildly interesting fact: UA-cam classified your comment as probable spam, probably because of the word "hire". Also, these videos are significantly more organized than my real-life lectures.
Kumari Yamala If maxHeapify is coded iteratively, or with tail recursion that the compiler optimizations unwind (probably pretty standard now, though I am not a compiler guy), it takes Theta(1) space, and O(lg n) time. The recursive version, without tail recursion optimization would take, worst case, Theta(lg n) space.
In a MaxHeap, siftUp is for when an element might be larger than its parent, and might have to move up one (or more) levels. When you insert, you stick the new element as the last leaf, but maybe it is bigger than its parent and grandparent, so it needs to move up. siftDown would be for when an element is in danger of being smaller than one of its children. When deleting the maximum element at the root, when you swap the last leaf into its place, that element is likely not the new max element in the heap, so it probably has to move down within the heap, maybe many levels.
Algorithms with Attitude So this means siftUp is usually called during insertion while siftDown is usually called during deletion after the root and last leaf swapped. Is this a correct interpretation of this?
Yes. siftDown is also called during the linear-time build-heap operation, and if you allow keys to arbitrarily be changed, either can be called there, depending on if the key gets larger or smaller.
@@AlgorithmswithAttitude Good one. Actually, many years ago, I did implement heapsort, and instead of just plucking off the largest element, I grabbed the 2 largest (root and larger child), and both myself and someone else (he implemented it too), saw about a 2% to 3% speedup overall. I called it "double pop" heapsort, since it is "popping" 2 elements each "pass".
@@davidjames1684 If you go into my heaps playlist, you one of the videos is on optimization. By changing the way that maxHeapify works, you can nearly cut your expected comparisons in half, which should give you a much bigger speed up (though not 50%).
@@davidjames1684 I think if you are talking about small changes in efficiency, you need to make sure that big issues are handled first. So here, where I show items swapping during maxHeapify? That isn't the efficient way to do it, even if you do want to compare an item against its children while moving down. It is likely more efficient to copy the item elsewhere, do your comparisons moving things up (without copying the first item during that process), and only have one copy at the end. I would not expect popping two items at once to be better, in that both will usually go back down to the near bottom of the heap, but will do so on different paths, ending up in different parts of the heap. Obviously, I don't know how you implemented your double pop, but what savings could it give you? If, without comparing the root to its children, you check which child is bigger and one of the pops goes there, you are basically saving one of the the comparisons that the optimization in the other video already saves. That one comparison per two pops might save you a small amount of time, but it would already be saved with the other optimization.
amusing and effective explanation - learned it in O(1). Thank you
One of the best video series on the topic. I call it an art to be able to explain complex concepts and definitions with ease and and add a pinch of humor as well.
David this is awesome!!
This channel really is algorithms with attitude! You keep me awake with all those not-so-subtle jokes. But besides that thank you so much, you've really helped me in not only catching up in my data structures class, but also in getting ahead! Thank you!
"like a fart in the storm" :) Man you are great!
+Artem Aleksandrovich Kost Thought I could slip that one by without anybody noticing...
Just like a fart during a storm :) By the way great explanation
I spit my coffee again
fucking amazing
lmaoooo. i wish all of my professors are like him
Visually effective while not skipping the analysis part. This is amazing.
"All those moments will be lost in time, like farts in storm."
Love how concise these are.
Our college would literally hire you if you applied for a job. You're HEAPS and bounds better than the professors here who have their doctorates
+Brandon Bryant
Thank you, though I suspect I wouldn't be hired so easily: it is pretty hard to get a professorship, each of your professors was probably chosen out of 100+ applicants. Crazy, right? Hopefully that will insulate their egos should one of them see this comment (or you could delete it).
Mildly interesting fact: UA-cam classified your comment as probable spam, probably because of the word "hire". Also, these videos are significantly more organized than my real-life lectures.
thank you verry much Mr , the heaps are not a problem anymore .
+amine lagab You are welcome.
fantastic video !
Who the F dislikes these amazing resource videos!
Thanks you, very charismatic explanation!
Nice explanation. thanks
Great videos, man! :D
I like this guy ; )
Thanks for your videos
This has been very helpful.
Really helpful! Thank you very much :)
Thank u so much!! That was very useful
Good Video, Really Helped =)
Amazing! Simple short and fun.
P.S. where's the attitude? :D
Seems like I should insult the snot outta you here, just to answer that question, right?
Naaa I`m good. Keep em coming.
100Thanks
You use delete max which has space of o(logn) because of recursive calls but it is o(1)
Kumari Yamala If maxHeapify is coded iteratively, or with tail recursion that the compiler optimizations unwind (probably pretty standard now, though I am not a compiler guy), it takes Theta(1) space, and O(lg n) time. The recursive version, without tail recursion optimization would take, worst case, Theta(lg n) space.
Can you explain the difference between siftUp vs siftDown and when they are used?
In a MaxHeap, siftUp is for when an element might be larger than its parent, and might have to move up one (or more) levels. When you insert, you stick the new element as the last leaf, but maybe it is bigger than its parent and grandparent, so it needs to move up.
siftDown would be for when an element is in danger of being smaller than one of its children. When deleting the maximum element at the root, when you swap the last leaf into its place, that element is likely not the new max element in the heap, so it probably has to move down within the heap, maybe many levels.
Algorithms with Attitude So this means siftUp is usually called during insertion while siftDown is usually called during deletion after the root and last leaf swapped. Is this a correct interpretation of this?
Yes. siftDown is also called during the linear-time build-heap operation, and if you allow keys to arbitrarily be changed, either can be called there, depending on if the key gets larger or smaller.
awsome！！Thank u
The video is great but I'm a little taken aback by the speaker facing the other way
Thanks
I tried implementing this but I got myself into a heap of trouble.
I hope you were able to sort it out.
@@AlgorithmswithAttitude Good one. Actually, many years ago, I did implement heapsort, and instead of just plucking off the largest element, I grabbed the 2 largest (root and larger child), and both myself and someone else (he implemented it too), saw about a 2% to 3% speedup overall. I called it "double pop" heapsort, since it is "popping" 2 elements each "pass".
@@davidjames1684 If you go into my heaps playlist, you one of the videos is on optimization. By changing the way that maxHeapify works, you can nearly cut your expected comparisons in half, which should give you a much bigger speed up (though not 50%).
@@AlgorithmswithAttitude I wonder what happens if you try both.
@@davidjames1684 I think if you are talking about small changes in efficiency, you need to make sure that big issues are handled first. So here, where I show items swapping during maxHeapify? That isn't the efficient way to do it, even if you do want to compare an item against its children while moving down. It is likely more efficient to copy the item elsewhere, do your comparisons moving things up (without copying the first item during that process), and only have one copy at the end. I would not expect popping two items at once to be better, in that both will usually go back down to the near bottom of the heap, but will do so on different paths, ending up in different parts of the heap.
Obviously, I don't know how you implemented your double pop, but what savings could it give you? If, without comparing the root to its children, you check which child is bigger and one of the pops goes there, you are basically saving one of the the comparisons that the optimization in the other video already saves. That one comparison per two pops might save you a small amount of time, but it would already be saved with the other optimization.
Isn't quicksort n^2, worst case?
+Bizorke It is, but it's expected runtime is faster than heapsort. Do I say otherwise? Please post a time in the video.
Algorithms with Attitude No. Sorry my mistake - I was only considering the worst case and not the average case.
Thanks for the response.
"100Thanks"
thanks sir
your avatar is scary
Scary Legos?
yes, creepy like a Chucky doll or Furby
Are Furbies (Furbies?) generally considered creepy? Regardless, stay brave, Herotruth.
@Herotruth your avatar is scary
How did I not notice that?
Im not that far right hahaha