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!!
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.
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
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)
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.
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
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!
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.
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.
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.
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.
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.
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)
![Eminem - Temporary (feat. Skylar Grey) [Official Music Video]](http://i.ytimg.com/vi/ZaK9Wi5ho0o/mqdefault.jpg)
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
pro tip: playback speed 2x
I also did that
@@arjunmr2631 who
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.
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 really liked all the example heaps.
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
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
@7:15, arent heaps always represent a binary tree but with structural ordering?
Wow! more in depth videos on balancing tree and tree rotation implementation pls
Golden content
the best video so far....nice explanation
Clear and Conceptual
These videos are very well made and helpful
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.
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.
In short: I subscribed to you channel!
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
7:44 but two things are pointing to the same node?
Great explanation! Thanks!
Very good video! thanks
Thank you very much
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)
Fantastic video! Keep up the good work.
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.
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
Is that always lawful to change the root of the heap?
Thank you!
Heap is a complete tree, but you are referring the opposite
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.
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
Thanks for explaining concepts nicely!
Thank you very much for making this video.!
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
Thanks!!!
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.
Nice explanation, thank you
great stuff, who needs a CS degree?
nice 😊👍 thanks
bro heaps are complete binary trees right.....
Still you didn’t clear main concept on priority Queue
deserve our prof's salary
can u tell me what is heap invariant??
Watch the video?
Grt explNtion
do you have a code on that circles
I love your voice
I absolutely don't lol
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)
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.
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.
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
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.
Watch at 1.25x
*1 2 3 4 4 5 9 8 14 22* _isn't this what first answer should be...
u r best!11!
Like if you are here for a Dijkstra assignment
Do you have the code of that with priority queue? 🤔
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.
Play at lest 1.25 speed, but great content
You sound like MoistCritikal before he got into chain smoking
Neat video. I'm not sure I liked your example tho.
Om shanti k
1.5x
dude for real
4:50
bad
i still like you as a person though
9:40 you mean BREADTH first search, not BEST first search, right?
best is correct
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)