Or is it because you already learned it for two hours and it's easier with a new visual explanation it makes sense now? 🤔 I'm visual so it may be the video.😁
This is a good explanation. It's also worth mentioning that the time complexity of this algorithm is log(n) for inserts and deletes. For example, when you add a new node, it will only have to be swapped at most log(n) times, where n is the total number of nodes in the tree.
Maybe you missed that part, but he said that we want our binary heap to be perfectly balanced. In that case the insertion showed in the video is correct.
@@Yazan_Majdalawi we are trying for perfectly balance, suppose we have imbalance by factor 1 (suppose height(left)-1 === height(right)), now if we are inserting a new node, if we insert it to left again then the factor will still be 1, but if we insert to the right our factor will be zero and heap will be perfectly balanced The complete binary tree shape is also a valid but the balance factor can be 1 (which is allowed).
I missed a lecture at university the other week and ended up doing a test without having any idea what a heap was or how it worked; Your video is clear and easy to understand, and I wish I'd looked sooner. Thank you.
I'm more familiar with the implementation as a complete tree ("filling each level from left to right") as it's easier to implement in a vector which eploits the contiguity in memory. This more AVL styled implementation is still interesting I have to say
Somewhat amusingly, this has the same flaw that the video gave for just using an array, but the "flaw" in question is so minor that it's still usually more efficient than using pointers like in a traditional binary tree or linked list.
To make a complete binary tree, you go from top to bottom, left to right ALWAYS. The insertion in this video is not correct... however, the information he presents is very helpful!
thank you so much, i was learning and checked my results with some homework awnsers and got really confused because the homework only showed the end result not the steps inbetween, know i know it was the left to right thing
Binary tree and Binary heap are different. Both have different usage. A binary tree is for storing data while the binary heap is use primarily for a priority queue, either min or max.
Heck yeah I discovered you on CS50 w/David&Doug earlier this year and can't believe I haven't found this yet.! Thanks Brian for EVERYTHING you do homie ✌️
your way of explaining and the sound of your voice and the type of things you talk about is all so great and makes me watch hours and not feel the time. Amazing videos man you deserve much more subscribers, hope you upload more♥️♥️♥️♥️♥️
amazed to see this video in just 8 minutes we need to give at least an hour to learn the same concept at other places . Also it is helpful to understand the concept with the real life example so that we also know the applications. please create more videos on data structure . Thanks!!
thanks for explanation. it was so easy to follow. i didnt get heaps and trees but now they look really obvious. thanks man. i was so frustrated now im happy
Thank you for the explanation. I was just studying about it during a computer science -Python course on CodeAcademy and they didn't explain what's the real-life usage for this data structure, which is a shame. If I'd like to go deeper and understand the process that led to the creation and planning of this data structure, where would you recommend me to read or watch?
The insertion is definitely not what many and I have learned, but still the invariant that the n-th node's child node should be 2n and 2n+1 remains unchanged.
@@MohammedAli-p7e9d The problem is the order of insertion in the video which is 0, 1, 2, 3, 5, 4, 6, 7, 11, 9, 13, 8, 12, 10, 14. You have 2 implementations possible in an array or in a tree. Let’s look at array because it is the simplest. the position of the root is 0, the position of the parent node floor(P/2j, the position of the right child is 2P and the left is 2P+1. The insertion is always made at position N, so always O(1) plus the percolation O(log n) and that garanties the height of the right subtree has at most 1 in difference with the height of the left subtree and the rest is like what you have in the video. So here the order of insertion is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, … Now the link binary tree implementation in the next comment.
@@MohammedAli-p7e9d With a binary tree with links, the problem is where to insert a new element. Let’s suppose we put the height of the subtree in each node. Now we will start with a tree that is full on tree level so that all the child nodes of a parent they have the same heights. What rule should we use to find an insertion point? We know percolation is O(log nj so whatever we use it must O(log n) or better. Lets use the rule if the height of the subtree are equal we go left else we go right. In our exemple, we go all the way left and insert then percolate and ajust the height of each father node. The seconde element we add goes to the right first because the 2 subtree have unequal heights the left all the way down insert then percolate and ajust the height of each father node. Imagining that the root is at position 0 the insertion order is 7, 11, 9, 8, 10 and the this rule breaks because it would add a node on level 5 while level 4 is not full. I tried to think of a way to obtain the order … (i will come back, i have to work)
@@MohammedAli-p7e9d Let me correct myself. IT is not wrong just inefficient. He has to keep 2 counts in each node, one for of all the nodes in the left subtree and one for of all the nodes in the right subtree. There is a better way. By using the total element count plus one and from the most significant bit to the least, from the root, go left on a 0 and go right on a 1.
Excellent video, nice job. Is insertion left-child first or left-most-leaf first? Left-most-leaf would be consistent with array visualization of heaps?
The explanation is quite good, but there are some small mistakes such as insertation and when you said the child cannot be smaller than the parent in Binary Heaps, that all depends if the Binary Heap is Min or Max, so that rule only exists when we define the Binary Heap!! Great vid!
No, not a Huffman tree, a balanced binary tree. "... at the expense of performance ..." I don't think you know what you are talking about. You are comparing apples to oranges.
@@vr77323 In the graph at 6:44 the root element is null. So we could just swap it with the smallest of its children and repeat, making the first step (setting 11 to be the new root) obsolete. In the animation it would look like the value null is propagating downwards, kinda like air bubbles in water (but upside down) or the gap between cars in a traffic jam.
@@powerdust015lastname4 What you propose is equivalent. If after that you move the 11 in the hole and you move the 11 toward the root until the parent is smaller.
This video is overcomplicating binary heap. Watch Sebastian Lague's Heap Optimization video in his A* Pathfinding series. The way he explains makes more intuitive sense.
I have learnd more in 8 min with you than 2 h in the university.
agree. it's so different when they explained first why you're doing this than focusing on how to do it.
True, GOD! it is frustrating when my lecturer would give us homework first before explaining which make the whole thing pointless.
this
Or is it because you already learned it for two hours and it's easier with a new visual explanation it makes sense now? 🤔
I'm visual so it may be the video.😁
Different styles make people learn more!
This is a good explanation. It's also worth mentioning that the time complexity of this algorithm is log(n) for inserts and deletes. For example, when you add a new node, it will only have to be swapped at most log(n) times, where n is the total number of nodes in the tree.
Yeah, log(n) is basically the depth (amount of rows) of the heap, so that makes sense.
@@dominiquefortin5345 isnt he finding it by having a counter in every node?
@@alpharudiger1193 No he keeps 2 in each nodes. One for the right subtree and one for the left subtree. Not very efficient.
At 4:25, I think the insertion is wrong. We always add it to the leftmost en.wikipedia.org/wiki/Binary_heap#Insert
Agree! Insertion is wrong.
Agree
Maybe you missed that part, but he said that we want our binary heap to be perfectly balanced. In that case the insertion showed in the video is correct.
@@georgiatanasow6658 Why though? is there a benefit for doing it that way, compared to the easy way of filling the level from left to right?
@@Yazan_Majdalawi we are trying for perfectly balance, suppose we have imbalance by factor 1 (suppose height(left)-1 === height(right)), now if we are inserting a new node, if we insert it to left again then the factor will still be 1, but if we insert to the right our factor will be zero and heap will be perfectly balanced
The complete binary tree shape is also a valid but the balance factor can be 1 (which is allowed).
I missed a lecture at university the other week and ended up doing a test without having any idea what a heap was or how it worked; Your video is clear and easy to understand, and I wish I'd looked sooner. Thank you.
I'm more familiar with the implementation as a complete tree ("filling each level from left to right") as it's easier to implement in a vector which eploits the contiguity in memory. This more AVL styled implementation is still interesting I have to say
This was my first time seeing an AVL type of implementation for a heap. I was always taught the complete tree structure as well
Somewhat amusingly, this has the same flaw that the video gave for just using an array, but the "flaw" in question is so minor that it's still usually more efficient than using pointers like in a traditional binary tree or linked list.
@@rektdedrip There is no reason to do the AVL type thing.
To make a complete binary tree, you go from top to bottom, left to right ALWAYS.
The insertion in this video is not correct... however, the information he presents is very helpful!
and also during deletion, the right-most element is sent to the root, isn't it? to preserve the said property?
@@pursadas yes, as far as i remember
thank you so much, i was learning and checked my results with some homework awnsers and got really confused because the homework only showed the end result not the steps inbetween, know i know it was the left to right thing
He isn't making a binary tree, though, but a binary heap. Which looks a lot like a binary tree, but is faster - also because it allows for duplicates.
Binary tree and Binary heap are different. Both have different usage. A binary tree is for storing data while the binary heap is use primarily for a priority queue, either min or max.
Amazing video. The most detailed and "to the point" explanation of binary heaps I have seen. Many thanks. Keep it up!
I love the presenter! Explain so well, so concisely!!!!
Easily a 5 star video. You've earned a sub, my friend.
PERFECT video. Not boring and super informative. Covering all exceptions and key concepts. Thank u!
please make some more videos on different Algorithms like sorting Array algorithms, greedy algorithms, graphs implementations, etc.
Explained in very structured way.
Heck yeah I discovered you on CS50 w/David&Doug earlier this year and can't believe I haven't found this yet.! Thanks Brian for EVERYTHING you do homie ✌️
your way of explaining and the sound of your voice and the type of things you talk about is all so great and makes me watch hours and not feel the time.
Amazing videos man you deserve much more subscribers, hope you upload more♥️♥️♥️♥️♥️
Really nice video! I could watch animations of values getting inserted and deleted on binary trees all day.
Great video! I was looking for a quick refresher to help me implement a priority queue to use in the A* algorithm.
Amazing how I can learn 20x as much from a 20 minute video than I did in a two hour lecture
amazed to see this video in just 8 minutes we need to give at least an hour to learn the same concept at other places .
Also it is helpful to understand the concept with the real life example so that we also know the applications.
please create more videos on data structure .
Thanks!!
I'd love a re-visit of this topic, with a comparison of a binary tree, including big O analysis.
A heap is a kind of binary tree
@@coffeedude Heap is a binary tree.
@@dominiquefortin5345 Yeah, it's a specific kind of binary tree. That's what I meant : )
@@dominiquefortin5345 Yeah, it's a specific kind binary tree. That's what I meant : )
this is clear and concise, thank you 🌟
This is the best explanation I have seen about heap. Big thumbs up!
Hats off for the graphics. It was very much easy to understand
this is the best illustration of a binary heap.
thanks for explanation. it was so easy to follow. i didnt get heaps and trees but now they look really obvious. thanks man. i was so frustrated now im happy
Thank you for the explanation.
I was just studying about it during a computer science -Python course on CodeAcademy and they didn't explain what's the real-life usage for this data structure, which is a shame.
If I'd like to go deeper and understand the process that led to the creation and planning of this data structure, where would you recommend me to read or watch?
But for understanding, code it and play with it. It is only 3 functions insert, delete, size.
Bruh this was so much better explained than all of the videos with wayyyy more views on YT
BRIAN GET SOME FREE TIME AND UPLOAD AGAIN WE NEED YOU HAHAHAHAHAH I LOVE U
Thank You So Much brother for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
thank you for the help on the CS51 PSET Brian...very much appreciated
@@dominiquefortin5345 whomp whomp
I think the insertion operation at 4:27 might be wrong, since the n th node's child node should be 2n and 2n+1.
The insertion is definitely not what many and I have learned, but still the invariant that the n-th node's child node should be 2n and 2n+1 remains unchanged.
In an array, yes, but he is using a binary tree.
Amazing explanation and animation. Keep it up
need all topics of data structure please 😃
Thanks for the clear explanation
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, it is not Amazing
@@dominiquefortin5345 yeah you are correct, thanks for pointing it out
@@utkarshsharma1185 Let me correct myself. But the author uses a space inefficient way by keeping 2 counter in each node. There are better ways
thank you very much. very intuitively explained
that is a great explanation thanks
The video teaches very much in a short time. Great 👌
Subscribed! Awesome explanation. ❤
Recognized Brian Yu by voice. Great video, thank you very much, I am your fan
This actually helped me understand how Heap Sort works.
thank you bro, now i understand more and expand my knowledge with this new type of data structure.
(really helped in greedy algorithms btw)
4:42 Where do we add 9th node? Do we add under 5th node or we add under 6th node?
Thank you very much for this video!
Priceless lessons
Brian, Thanks for simplifying.
Amazing and clear explanation...
best explaination ever, wish i watched this before my algorithm exam
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, not good
@@dominiquefortin5345 can you tell me what are the wrong points?
I am still learning.
@@MohammedAli-p7e9d The problem is the order of insertion in the video which is 0, 1, 2, 3, 5, 4, 6, 7, 11, 9, 13, 8, 12, 10, 14. You have 2 implementations possible in an array or in a tree. Let’s look at array because it is the simplest. the position of the root is 0, the position of the parent node floor(P/2j, the position of the right child is 2P and the left is 2P+1. The insertion is always made at position N, so always O(1) plus the percolation O(log n) and that garanties the height of the right subtree has at most 1 in difference with the height of the left subtree and the rest is like what you have in the video. So here the order of insertion is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, … Now the link binary tree implementation in the next comment.
@@MohammedAli-p7e9d With a binary tree with links, the problem is where to insert a new element. Let’s suppose we put the height of the subtree in each node. Now we will start with a tree that is full on tree level so that all the child nodes of a parent they have the same heights. What rule should we use to find an insertion point? We know percolation is O(log nj so whatever we use it must O(log n) or better. Lets use the rule if the height of the subtree are equal we go left else we go right. In our exemple, we go all the way left and insert then percolate and ajust the height of each father node. The seconde element we add goes to the right first because the 2 subtree have unequal heights the left all the way down insert then percolate and ajust the height of each father node. Imagining that the root is at position 0 the insertion order is 7, 11, 9, 8, 10 and the this rule breaks because it would add a node on level 5 while level 4 is not full. I tried to think of a way to obtain the order … (i will come back, i have to work)
@@MohammedAli-p7e9d Let me correct myself. IT is not wrong just inefficient. He has to keep 2 counts in each node, one for of all the nodes in the left subtree and one for of all the nodes in the right subtree. There is a better way. By using the total element count plus one and from the most significant bit to the least, from the root, go left on a 0 and go right on a 1.
Excellent explanation
I t seems so. I just came in to explore number theory. 💕 the good teachers in different fields.
Amazing video. Thank you!
Amazing explanation. thanks
Such an amazing video, thanks
Just 1 mins and 40 sec into this video and already liked and subbed.
THIS IS MORE THAN GREAT THIS IS INCREDIBLE
Great Explaination thanks
Great animation! Learned a lot.
Could you make a video on TRIE ?
Please make video on radix Heap, as It is difficult to understand. Thanks for this awesome video 👍👍
Really nice explanation, so thank you so much.
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, not nice
great video, thank you
keep the good work sir
My god, you are so amazing please make more videos, we need you
Thanks for the video
Great explanation!
@@dominiquefortin5345then tell me the right one?
Amazing💯
Thanks Brian!
@@dominiquefortin5345 doesn’t matter. The man is a legend
But if you want to search for one specific in the bottom of the list you don't know where it is.
Excellent video, nice job. Is insertion left-child first or left-most-leaf first? Left-most-leaf would be consistent with array visualization of heaps?
Insertion should be donne at the end of the array, no left-child or right-child.
thank you, it was helpful
at 4:30 in video, you have shown wrong complete binary tree, stop teaching wrong concepts.
thank you so much
Please do cover more portion of ds and algo. Lots of Love. Thank You
Feel free to suggest any data structures and algorithms you'd like to see covered!
Good explanation
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, it is not good
well explanation !
Except the information in this video is just so slightly wrong, that people will not know it is bad.
very helpful!
Great vid, on an unrelated note, you sound just like the dude from CS50 course
thanks dude!
I think it would have been more helpful if you were more specific when discussing time complexity, but I still found this video useful
how would you code something like this?
nice video :D
at first I thought this is just a binary tree
It is a binary tree, it is a balanced binary tree. It is not a binary search tree.
@@dominiquefortin5345 at first I thought this is just a binary tree
What is the complexity of searching an element?
讲得不错！！
Thank you
The explanation is quite good, but there are some small mistakes such as insertation and when you said the child cannot be smaller than the parent in Binary Heaps, that all depends if the Binary Heap is Min or Max, so that rule only exists when we define the Binary Heap!! Great vid!
He did say that we will be talking about min-heap for this explanation
It would be cool to show how that would work in python or some other language
You made this fucking easy, thank god.
oops "2:99 Insertion" - 3:01 is the time
thanks
would have been nice to show how this is better then a linked list.
Binary heap should be a complete binary tree , that means left to right. The insertion is wrong.
the insertion is wrong
Just a heads up, your timestamp for Insertion is not valid!
So basically a Huffman tree. Which of course could be implemented as an array (albeit, at the expense of performance).
No, not a Huffman tree, a balanced binary tree. "... at the expense of performance ..." I don't think you know what you are talking about. You are comparing apples to oranges.
@@dominiquefortin5345 Yeah I honestly don't know what I was thinking there. I may have answered that one before I had my coffee! Cheers....
Good work! Btw. consider investing in a microphone, its worth it...
6:44 why take a low priority element? you could just skip this step and swap the smallest children with null instead
Could you elaborate on that? I don't think I understand what you mean by setting smallest children to null
@@vr77323 In the graph at 6:44 the root element is null.
So we could just swap it with the smallest of its children and repeat, making the first step (setting 11 to be the new root) obsolete.
In the animation it would look like the value null is propagating downwards, kinda like air bubbles in water (but upside down) or the gap between cars in a traffic jam.
@@powerdust015lastname4 What you propose is equivalent. If after that you move the 11 in the hole and you move the 11 toward the root until the parent is smaller.
This video is overcomplicating binary heap.
Watch Sebastian Lague's Heap Optimization video in his A* Pathfinding series.
The way he explains makes more intuitive sense.
keep more in algorithm
Why is it that videos on TH-cam explain stuff better while I'm paying a ridiculous amount of money just to attend a school?
I don't like this. Just add nodes by layers.
Brian is that you? I'd recognise that voice from a mile away
I'm a middle child. Always left out and forgotten.
this will be thanos favorite data structure..