Every time I come back to refresh my memory on an algorithm or data structure, I get excited when I see that you have a video covering it. Thank you for the animations and teaching in such a clear way!
I learned your Graph Theory Course to this part and I didn't understand PQ so I come here to learn it. I enjoy the way you teach with the animation and other stuffs very much. Thanks man!!
By your definition, a heap is a tree. However, one of the differences between a tree and a graph is that in a tree, every child can only have one parent, and yet in 7:34, the node with 6 in the third level has two parents (one a 3 and ther other is also 6), so it can't be a tree but it is a heap?
Yeah, that example is questionable. Although I still maintain that the whole structure is a tree because there are no cycles. What I should have done is made the edges directed so that there is no ambiguity regarding which node is the parent/child of which.
@@subbuktek Because the diagram put the other '6' as one level above, the same reason that the '3' on level 2 is a parent. I know what you are alluding to, if you can assume the '6' on level 2 is a child instead of a parent, you can also assume the '3' is a child, not a parent, in that case it still can't be a heap
When implementing, every node/element of the binary tree has a value, and two pointers. These two pointers can either point to another node (which is under the current node) or to nothing. So they can technically have 0 children, but they always have two pointers, which are both pointing to nothing.
Are the edges bidirectional? I would think they only go in one direction and that displaying the edges vertically or diagonally implies a direction from the higher node to the lower node. So, assuming the edges are directional, breaking with the convention of displaying the directions from top to bottom would mean we should display them as arrows instead of lines.
4:05 If two elements in the priority queue have the lowest value in the queue, doesn't that mean the number polled from the queue isn't necessarily the smallest number in the queue?
No. This example is not how it would be implemented. In a binary tree, the order would be as his examples towards the end of the video demonstrate. You can have two nodes with the same value (priority), where they might be a child of the node that is removed. The node that is left over, would then bubble up and take the place of the just removed node.
Best first search isn't an algorithm - it's a category of algorithms which require the next-best item or thing in the data structure (where "best" is determined by a weight or a number) at each iteration (A* does this to find the next "best" movement choice for pathfinding in a graph, but the other algorithms he mentions find the next "best" choice in their respective implementations as well)
I think that he made fault when validating trees mentioned in this video, I think some of them are not complete binary trees so they are not heap, since heap must be a complete binary tree
4:21 "As human we can see the numbers visually inside the priority queue, and look and know what one is the smallest to poll". Actually not quite, if we have 1 million numbers in the queue, human will have a tough time identifying the number to poll just as an inefficient programmed machine does.
It does not have to be a perfect tree, the heap simply must be filled from left to right, if you have nodes with children then the next two nodes over at that height have no children and children respectively then that is not a valid heap. Branching factor only affects where you will start your buildHeap method whether that may be max or min, for instance if you had a heap with 3 child nodes the point at which the last possible node with children would be at will be floor of heapSize/3 (ROUGHLY) depending if were talking pseudo code and the starting index is 1 or actual code at 0.
A heap does not have to be a binary tree. It's typically implemented in this way though. I think that's where the confusion comes from. Although the idea of it being a perfect tree makes me think you misunderstand the heap idea. It doesn't have to be perfect (or even complete). It just has to follow the heap invariant.
May I ask a question? when you took an example of what a priority queue is and the instruction asked us to add 2,4,5,9, WHY these numbers were not added with the poll operation?
Yeah, from 3:35 we can see the instruction and take poll and add operations. Firstly poll() we get 1, secondly add (2) we get 2, thirdly poll() you said it happened to be 2 not 3?.... I watched the video again and realized it was because the pink circle didn't pop up with the arrow at the same time, but now I understood it. Thank you very much for your reply! your video is very good!
He actually said heap isn't *necessarily* a binary tree, with heaps that are not implemented as binary tree, they are called binomial heap (as opposed to binary heap)
The complexity for building a heap isn't correct. It takes 'O(nlog(n))' to build a heap, because you are doing 'n' additions.Same would go for a priority queue too.
A queue is usually understood like an ordered list. A priority queue is a kind of list where it's structured so you can get things marked with a more important "priority" faster and easier. Heaps are a good way to think about implementation, but they can be implemented a number of ways.
Every time I come back to refresh my memory on an algorithm or data structure, I get excited when I see that you have a video covering it. Thank you for the animations and teaching in such a clear way!
Been reviewing some concepts for a FAANG interview and your videos are the best for clear and concise review of data structures
I love the is this a valid heap section, very useful. Newbies like me often have many “stupid questions” like these, but hardly find answers.
What a beautiful animation, my eyes were on my laptop cause the colour combination was so good to watch.
xd
@@KadaXuanwu ?
@@sword013 Vada Pav
This is what I was looking, How PQ and heap is related and was getting confused b/w these two. Can't thank you enough.
pro tip: playback speed 2x
I also did that
@@arjunmr2631 who
I really liked all the example heaps.
this is awesome! thanks for asking questions testing us so we can try to answer it instead of just giving the answer
Hy
@@geetanjalijangid876 hlo
I learned your Graph Theory Course to this part and I didn't understand PQ so I come here to learn it. I enjoy the way you teach with the animation and other stuffs very much. Thanks
man!!
Thank you! I couldn't find any other video on this topic
I don't think 7:35 is a heap because it's not a tree. In order for it to be a tree, I think each child can have only 1 parent
this is a tree. look at it carefully every parent has child in it.
the best video so far....nice explanation
By your definition, a heap is a tree. However, one of the differences between a tree and a graph is that in a tree, every child can only have one parent, and yet in 7:34, the node with 6 in the third level has two parents (one a 3 and ther other is also 6), so it can't be a tree but it is a heap?
Yeah, that example is questionable. Although I still maintain that the whole structure is a tree because there are no cycles. What I should have done is made the edges directed so that there is no ambiguity regarding which node is the parent/child of which.
Why do you think the other '6' is a parent? ...
@@subbuktek Because the diagram put the other '6' as one level above, the same reason that the '3' on level 2 is a parent. I know what you are alluding to, if you can assume the '6' on level 2 is a child instead of a parent, you can also assume the '3' is a child, not a parent, in that case it still can't be a heap
Golden content
@7:15, arent heaps always represent a binary tree but with structural ordering?
Heap need to be always binary tree. They can be ternary also.
he missed some facts also. Heap needs to be complete binary tree. He called some of them heap while they weren't complete bt
Wow! more in depth videos on balancing tree and tree rotation implementation pls
7:44 but two things are pointing to the same node?
Binary trees have at most two children, right? Not more than two. But can also have 0 or 1 child. Like showed in the max heap diagram at 6:12
When implementing, every node/element of the binary tree has a value, and two pointers. These two pointers can either point to another node (which is under the current node) or to nothing. So they can technically have 0 children, but they always have two pointers, which are both pointing to nothing.
In short: I subscribed to you channel!
Clear and Conceptual
These videos are very well made and helpful
Fantastic video! Keep up the good work.
Are the edges bidirectional? I would think they only go in one direction and that displaying the edges vertically or diagonally implies a direction from the higher node to the lower node. So, assuming the edges are directional, breaking with the convention of displaying the directions from top to bottom would mean we should display them as arrows instead of lines.
Great explanation! Thanks!
actually, a heap also needs to be a complete binary tree. so the 3rd example is in fact not a heap.
that's Correct
That's the definition of binary heap. So completeness is not necessary for a heap.
4:05 If two elements in the priority queue have the lowest value in the queue, doesn't that mean the number polled from the queue isn't necessarily the smallest number in the queue?
No. This example is not how it would be implemented. In a binary tree, the order would be as his examples towards the end of the video demonstrate. You can have two nodes with the same value (priority), where they might be a child of the node that is removed. The node that is left over, would then bubble up and take the place of the just removed node.
Very good video! thanks
what is best first search? (same as breadth first search?)
Best first search isn't an algorithm - it's a category of algorithms which require the next-best item or thing in the data structure (where "best" is determined by a weight or a number) at each iteration (A* does this to find the next "best" movement choice for pathfinding in a graph, but the other algorithms he mentions find the next "best" choice in their respective implementations as well)
Is that always lawful to change the root of the heap?
Is the video slowed down?
Shouldn't a tree be a complete tree for it to become a heap? The second example you gave is not a complete tree right? Correct me if I'm wrong please.
ruclips.net/video/wptevk0bshY/видео.html at here
ok but the way he asked if 7 was a heap and said "yeah, it's a heap" :')
Is the heap a complete binary tree? At 7'17", the heap is not a complete binary tree.
Heaps are complete binary tree or almost complete binary tree
But you didn't mention it
He said they don't need to be binary trees right?
I think that he made fault when validating trees mentioned in this video, I think some of them are not complete binary trees so they are not heap, since heap must be a complete binary tree
do you have a code on that circles
Heap is a complete tree, but you are referring the opposite
can u tell me what is heap invariant??
Watch the video?
Thank you very much
great stuff, who needs a CS degree?
4:21 "As human we can see the numbers visually inside the priority queue, and look and know what one is the smallest to poll".
Actually not quite, if we have 1 million numbers in the queue, human will have a tough time identifying the number to poll just as an inefficient programmed machine does.
bro heaps are complete binary trees right.....
Thank you!
Thanks for explaining concepts nicely!
7:39 doesn't a heap have to be a perfect tree too?
Yes exactly. The branching factor for this heap is 3 so we cannot have nodes with just 2 children or ne child.
It does not have to be a perfect tree, the heap simply must be filled from left to right, if you have nodes with children then the next two nodes over at that height have no children and children respectively then that is not a valid heap. Branching factor only affects where you will start your buildHeap method whether that may be max or min, for instance if you had a heap with 3 child nodes the point at which the last possible node with children would be at will be floor of heapSize/3 (ROUGHLY) depending if were talking pseudo code and the starting index is 1 or actual code at 0.
A heap does not have to be a binary tree. It's typically implemented in this way though. I think that's where the confusion comes from. Although the idea of it being a perfect tree makes me think you misunderstand the heap idea. It doesn't have to be perfect (or even complete). It just has to follow the heap invariant.
May I ask a question? when you took an example of what a priority queue is and the instruction asked us to add 2,4,5,9,
WHY these numbers were not added with the poll operation?
Shaozhe Tang I'm not sure I correctly understand your question. Could you please rephrase it? Thank you.
Yeah, from 3:35 we can see the instruction and take poll and add operations. Firstly poll() we get 1, secondly add (2) we get 2, thirdly poll() you said it happened to be 2 not 3?....
I watched the video again and realized it was because the pink circle didn't pop up with the arrow at the same time, but now I understood it. Thank you very much for your reply! your video is very good!
Oops, sounds like a timing delay! Sorry for the confusion.
Polling means deleating not adding
7:16 i thought you said heap tree only applies to binary tree. this one has 3 branches. Great animation.
He actually said heap isn't *necessarily* a binary tree, with heaps that are not implemented as binary tree, they are called binomial heap (as opposed to binary heap)
i thought in a binary heap nodes have only one or two children nodes. 7:14min
It’s not a binary heap, it’s just a regular heap. Only binary heaps must satisfy the requirement with up to 2 children
Still you didn’t clear main concept on priority Queue
Thank you very much for making this video.!
I love your voice
I absolutely don't lol
Nice explanation, thank you
deserve our prof's salary
Thanks!!!
nice 😊👍 thanks
Grt explNtion
The complexity for building a heap isn't correct. It takes 'O(nlog(n))' to build a heap, because you are doing 'n' additions.Same would go for a priority queue too.
u r best!11!
Instead of asking me questions, you could have explained the time complexities better!
Priority queue != queue with priority im thinking?
A queue is usually understood like an ordered list. A priority queue is a kind of list where it's structured so you can get things marked with a more important "priority" faster and easier. Heaps are a good way to think about implementation, but they can be implemented a number of ways.
*1 2 3 4 4 5 9 8 14 22* _isn't this what first answer should be...
4:50
You sound like MoistCritikal before he got into chain smoking
Play at lest 1.25 speed, but great content
Neat video. I'm not sure I liked your example tho.
Like if you are here for a Dijkstra assignment
Do you have the code of that with priority queue? 🤔
Watch at 1.25x
Om shanti k
1.5x
dude for real
bad
i still like you as a person though