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
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.
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
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.
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)
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: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.
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.
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!
pro tip: playback speed 2x
I also did that
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.
Been reviewing some concepts for a FAANG interview and your videos are the best for clear and concise review of data structures
What a beautiful animation, my eyes were on my laptop cause the colour combination was so good to watch.
xd
@@KadaXuanwu ?
@@sword013 Vada Pav
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 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 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!!
@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
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!
Thank you! I couldn't find any other video on this topic
Golden content
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
the best video so far....nice explanation
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.
7:44 but two things are pointing to the same node?
Clear and Conceptual
These videos are very well made and helpful
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)
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
ok but the way he asked if 7 was a heap and said "yeah, it's a heap" :')
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.
Fantastic video! Keep up the good work.
Heap is a complete tree, but you are referring the opposite
Is that always lawful to change the root of the heap?
Great explanation! Thanks!
Is the heap a complete binary tree? At 7'17", the heap is not a complete binary tree.
Thank you very much
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
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.
th-cam.com/video/wptevk0bshY/w-d-xo.html at here
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)
great stuff, who needs a CS degree?
bro heaps are complete binary trees right.....
Still you didn’t clear main concept on priority Queue
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
Thank you!
Thanks for explaining concepts nicely!
do you have a code on that circles
can u tell me what is heap invariant??
Watch the video?
deserve our prof's salary
I love your voice
I absolutely don't lol
Thanks!!!
nice 😊👍 thanks
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.
Grt explNtion
Thank you very much for making this video.!
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)
Nice explanation, thank you
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!
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
*1 2 3 4 4 5 9 8 14 22* _isn't this what first answer should be...
Watch at 1.25x
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.
You sound like MoistCritikal before he got into chain smoking
Play at lest 1.25 speed, but great content
4:50
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? 🤔
Om shanti k
1.5x
dude for real
bad
i still like you as a person though