What Is a Binary Heap?
Binary heaps are very practical data structures used in a variety of algorithms - including graph searching algorithms, compression algorithms, and more. Here, we explore how binary heaps work: what they're used for, how to add new data into them, and how to remove data from them once we're done.
0:00 Priority Queues
1:31 Binary Heaps
2:99 Insertion
6:04 Deletion
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
Пікірлер: 206
I have learnd more in 8 min with you than 2 h in the university.
@playanakobi4407
3 жыл бұрын
agree. it's so different when they explained first why you're doing this than focusing on how to do it.
@superannoymous5731
3 жыл бұрын
True, GOD! it is frustrating when my lecturer would give us homework first before explaining which make the whole thing pointless.
@maxdemian6312
2 жыл бұрын
this
@jkrigelman
Жыл бұрын
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.😁
@horaciomlhh
Жыл бұрын
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.
@NachitenRemix
Жыл бұрын
Yeah, log(n) is basically the depth (amount of rows) of the heap, so that makes sense.
@dominiquefortin5345
15 күн бұрын
Actually, his implementation of insertion is done in O(n) because he has to find the right leaf.
At 4:25, I think the insertion is wrong. We always add it to the leftmost en.wikipedia.org/wiki/Binary_heap#Insert
@vorun
2 жыл бұрын
Agree! Insertion is wrong.
@znacloudznacloud8568
Жыл бұрын
Agree
@georgiatanasow6658
Жыл бұрын
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
Жыл бұрын
@@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?
@amitdhaterwal8395
Жыл бұрын
@@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'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
@rektdedrip
Жыл бұрын
This was my first time seeing an AVL type of implementation for a heap. I was always taught the complete tree structure as well
@angeldude101
2 ай бұрын
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.
@dominiquefortin5345
15 күн бұрын
@@rektdedrip There is no reason to do the AVL type thing. This is bad, it makes insertion O(n) instead of O(log n).
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!
@pursadas
2 жыл бұрын
and also during deletion, the right-most element is sent to the root, isn't it? to preserve the said property?
@anushreevirtualgaming226
Жыл бұрын
@@pursadas yes, as far as i remember
@jellemiddendorf2572
Жыл бұрын
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
@kebman
Жыл бұрын
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.
@broccolidiego2053
Жыл бұрын
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.
I love the presenter! Explain so well, so concisely!!!!
Great video! I was looking for a quick refresher to help me implement a priority queue to use in the A* algorithm.
PERFECT video. Not boring and super informative. Covering all exceptions and key concepts. Thank u!
@dominiquefortin5345
15 күн бұрын
Not boring, tes, except the information in this video is just so slightly wrong, that people will not know it is bad.
Amazing video. The most detailed and "to the point" explanation of binary heaps I have seen. Many thanks. Keep it up!
@dominiquefortin5345
15 күн бұрын
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.
please make some more videos on different Algorithms like sorting Array algorithms, greedy algorithms, graphs implementations, etc.
This is the best explanation I have seen about heap. Big thumbs up!
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
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!!
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
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♥️♥️♥️♥️♥️
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, not amazing.
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.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
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 ✌️
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
thank you for the help on the CS51 PSET Brian...very much appreciated
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
@kiopsy7591
15 күн бұрын
@@dominiquefortin5345 whomp whomp
Hats off for the graphics. It was very much easy to understand
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
thank you bro, now i understand more and expand my knowledge with this new type of data structure. (really helped in greedy algorithms btw)
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
Please make video on radix Heap, as It is difficult to understand. Thanks for this awesome video 👍👍
Explained in very structured way.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
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?
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. But for understanding, code it and play with it. It is only 3 functions insert, delete, size.
Easily a 5 star video. You've earned a sub, my friend.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
Really nice explanation, so thank you so much.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, not nice
Brian, Thanks for simplifying.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
best explaination ever, wish i watched this before my algorithm exam
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, not good
this is clear and concise, thank you 🌟
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
Great animation! Learned a lot.
@dominiquefortin5345
15 күн бұрын
Yeah but, the information in this video is just so slightly wrong, that people will not know it is bad.
Amazing and clear explanation...
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, not amazing
Amazing explanation. thanks
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, not amazing
The video teaches very much in a short time. Great 👌
@dominiquefortin5345
15 күн бұрын
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
thank you, it was helpful
Please do cover more portion of ds and algo. Lots of Love. Thank You
@SpanningTree
3 жыл бұрын
Feel free to suggest any data structures and algorithms you'd like to see covered!
Amazing video. Thank you!
@dominiquefortin5345
15 күн бұрын
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
I'd love a re-visit of this topic, with a comparison of a binary tree, including big O analysis.
@coffeedude
9 ай бұрын
A heap is a kind of binary tree
@dominiquefortin5345
15 күн бұрын
@@coffeedude Heap is a binary tree.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. He made the insertion into a O(n) operation when it should be O(log n).
@coffeedude
15 күн бұрын
@@dominiquefortin5345 Yeah, it's a specific kind of binary tree. That's what I meant : )
@coffeedude
15 күн бұрын
@@dominiquefortin5345 Yeah, it's a specific kind binary tree. That's what I meant : )
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?
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. Insertion should be donne at the end of the array, no left-child or right-child.
Thank You So Much brother for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, it is not wonderful
Bruh this was so much better explained than all of the videos with wayyyy more views on YT
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
Such an amazing video, thanks
@dominiquefortin5345
15 күн бұрын
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
Great Explaination thanks
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, it is not great
Recognized Brian Yu by voice. Great video, thank you very much, I am your fan
@dominiquefortin5345
15 күн бұрын
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
very helpful!
Thanks for the clear explanation
@dominiquefortin5345
15 күн бұрын
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
@utkarshsharma1185
15 күн бұрын
@@dominiquefortin5345 yeah you are correct, thanks for pointing it out
Great explanation!
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. No, not great.
@aidynabirov5932
13 күн бұрын
@@dominiquefortin5345then tell me the right one?
THIS IS MORE THAN GREAT THIS IS INCREDIBLE
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, it is not incredible.
Excellent explanation
@brendawilliams8062
Жыл бұрын
I t seems so. I just came in to explore number theory. 💕 the good teachers in different fields.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. So no, it is not Excellent
This actually helped me understand how Heap Sort works.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
this is the best illustration of a binary heap.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
Priceless lessons
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
BRIAN GET SOME FREE TIME AND UPLOAD AGAIN WE NEED YOU HAHAHAHAHAH I LOVE U
thank you so much
Great vid, on an unrelated note, you sound just like the dude from CS50 course
My god, you are so amazing please make more videos, we need you
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
I think it would have been more helpful if you were more specific when discussing time complexity, but I still found this video useful
thanks dude!
讲得不错!!
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.
@DanielVazquez
2 жыл бұрын
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.
@dominiquefortin5345
15 күн бұрын
Yes, it is wrong.
@dominiquefortin5345
15 күн бұрын
@@DanielVazquez No, he as made the insertion O(n) instead of being of being O(log n)
keep the good work sir
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad. He has to correct it
well explanation !
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
Thank you
Good explanation
@dominiquefortin5345
15 күн бұрын
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
Thanks Brian!
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
@tarnum113
15 күн бұрын
@@dominiquefortin5345 doesn’t matter. The man is a legend
Just 1 mins and 40 sec into this video and already liked and subbed.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
Amazing💯
@dominiquefortin5345
15 күн бұрын
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
thanks
Could you make a video on TRIE ?
It would be cool to show how that would work in python or some other language
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!
@s0ulweaver
Жыл бұрын
He did say that we will be talking about min-heap for this explanation
nice video :D at first I thought this is just a binary tree
@dominiquefortin5345
15 күн бұрын
It is a binary tree, it is a balanced binary tree. It is not a binary search tree.
@VirtuelleWeltenMitKhan
15 күн бұрын
@@dominiquefortin5345 at first I thought this is just a binary tree
how would you code something like this?
You made this fucking easy, thank god.
@dominiquefortin5345
15 күн бұрын
Except the information in this video is just so slightly wrong, that people will not know it is bad.
keep more in algorithm
Good work! Btw. consider investing in a microphone, its worth it...
would have been nice to show how this is better then a linked list.
So basically a Huffman tree. Which of course could be implemented as an array (albeit, at the expense of performance).
@dominiquefortin5345
15 күн бұрын
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.
@FranzBiscuit
15 күн бұрын
@@dominiquefortin5345 Yeah I honestly don't know what I was thinking there. I may have answered that one before I had my coffee! Cheers....
But if you want to search for one specific in the bottom of the list you don't know where it is.
@dominiquefortin5345
15 күн бұрын
Yes exactly, which make insertion O(n) instead of O(log n) as it should be.
Brian is that you? I'd recognise that voice from a mile away
Insertion is wrong. When inserting, it is always done at the end of the array then the value bobbles up to keep the invariant.
What is the complexity of searching an element?
@dominiquefortin5345
15 күн бұрын
You can't directly search a heap. You have to transform it O(n) into a sorted list and then search that O(log n).
this will be thanos favorite data structure..
Just a heads up, your timestamp for Insertion is not valid!
damn thats Brian from CS50
Binary heap should be a complete binary tree , that means left to right. The insertion is wrong.
i was about to say i recognise the voice, cs50ai
I'm a middle child. Always left out and forgotten.
Why is it that videos on KZread explain stuff better while I'm paying a ridiculous amount of money just to attend a school?
@dominiquefortin5345
15 күн бұрын
Because, you can be sure that there are no errors like in this video. His method for filling the last level of the tree is wrong.
When we move up the number 11 to the root of the heap, we just need to see which root's children is smaller and repeat downwards. If none is smaller, the we are done! Note: We already know that 11 was brought from the bottom of the heap, so it must be either greater or equal to the two root's children.
@dominiquefortin5345
15 күн бұрын
"... must be either greater or equal to the two root's children ..." False, you only know that it is greater or equal to the left root's child because the 11 was on that sub tree. All the values on the right subtree can be greater than 11.
6:44 why take a low priority element? you could just skip this step and swap the smallest children with null instead
@vr77323
Жыл бұрын
Could you elaborate on that? I don't think I understand what you mean by setting smallest children to null
@powerdust015lastname4
Жыл бұрын
@@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.
@dominiquefortin5345
15 күн бұрын
@@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.
@Spanning Tree This is misinformation. You have to redo this video. How do you choose the position of the insertion in O(1)? The only way, I see with the objective of keeping the tree totally balanced, of choosing the position is by looking at all the leafs which would make the insertion O(n). That is stupid. Insertion has to be done in O(log n).
Brain from CS50 ?
the insertion is wrong
at 4:30 in video, you have shown wrong complete binary tree, stop teaching wrong concepts.
This method of organisation should be taught in schools.
this is overkill
Ooops, headache
Nice video. But unfortunately wrong!
@dominiquefortin5345
15 күн бұрын
Not all but the insertion is wrong
Why the pointless background "music" in an otherwise interesting video. Very distracting for some (like me...)
This is a terrible shape for a tree. Works for a linked data structure, but linked data structures are mostly terrible, so why would you do that?
Zero explanation of why. Zero insight. Just another crappy video about heaps walking through the exact steps of a specific algorithm for viewers to memorize
@dominiquefortin5345
15 күн бұрын
I would not go that far but the first step of insertion is wrong.
Thank you
Thank you